[23-24 동계 모각코] 4회차 결과

 

백준 5430 - AC

 

문제
선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다.
함수 R은 배열에 있는 수의 순서를 뒤집는 함수이고, D는 첫 번째 수를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다.
함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. 예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 수를 버리는 함수이다.
배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하시오.

입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 최대 100이다.
각 테스트 케이스의 첫째 줄에는 수행할 함수 p가 주어진다. p의 길이는 1보다 크거나 같고, 100,000보다 작거나 같다.
다음 줄에는 배열에 들어있는 수의 개수 n이 주어진다. (0 ≤ n ≤ 100,000)
다음 줄에는 [x1,...,xn]과 같은 형태로 배열에 들어있는 정수가 주어진다. (1 ≤ xi ≤ 100)
전체 테스트 케이스에 주어지는 p의 길이의 합과 n의 합은 70만을 넘지 않는다.

출력
각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다.

 

문제링크 - https://www.acmicpc.net/problem/5430

5430번: AC

 

문제 해결을 위해 고려한 조건 + 구현 방식

 

1. 입력받는 배열 원소 정수 처리

- 이 문제는 입력을 특이하게 괄호와 쉼표 모두 받기 때문에, [1:-1]범위의 부분만 가져와서 쉼표로 정수를 구분한 deque를 만들어줘야한다.

- 예를 들어, "[1,2,3]" 이렇게 큰 따옴표 안에 있는 것을 모두 입력 받는다. 하지만 처리는 정수(1,2,3)만 해야 하므로 쉼표로 구분을 해줘야 하고, 대괄호는 지워야한다. 만약 "[]"라고 입력을 받으면, 길이가 0인 부분에 대해서 예외처리로 빈 deque로 초기화를 해줘야 한다

# 배열이 비어있을 때
if n == 0:
    arr = deque(sys.stdin.readline().strip()[1:-1])
else:
    arr = deque(map(int, sys.stdin.readline().strip()[1:-1].split(',')))​

 

2. 입력받는 함수 문자열 리스트 변환

- 함수 문자열을 deque로 만드는데 'RR' 문자열이 있는 경우 배열을 두번 뒤집는 경우라 원래 배열과 같기 때문에 ''로 대체해서 operations 함수 리스트로 변환한다.

# 문자열 p를 함수 리스트로 변환
operations = deque(p.replace('RR', ''))  # 연속해서 두 번 R이 나오면 무시

 

3. 함수 연산 중 'R'의 개수에 따른 연산방식

- 함수 문자열을 함수 리스트로 변환한 deque를 탐색하여 연산을 수행할 때, R연산이 나올때마다 배열을 뒤집는 것이 아니라 R의 개수를 카운트하여 마지막에 R의 개수가 홀수냐 짝수냐에 따라 한 번만 뒤집거나, 뒤집지 않는다. (시간초과 방지)

- R의 개수가 짝수냐 홀수냐에 따라서 D연산 수행시 첫 번째 수를 제거할지, 마지막 수를 제거할지 판단한다.

# 배열에 있는 수를 순서대로 수행
for op in operations:
    # R 연산은 뒤집기, 뒤집은 횟수를 증가
    if op == 'R':
        r_cnt += 1
    # D 연산은 첫 번째 수를 버리기, 뒤집은 횟수에 따라 첫 번째 또는 마지막 수를 제거
    elif op == 'D' and n > 0:
        if r_cnt % 2 == 0:
            arr.popleft()  # 뒤집은 횟수가 짝수일 때는 첫 번째 수를 제거
        else:
            arr.pop()  # 뒤집은 횟수가 홀수일 때는 마지막 수를 제거
        n -= 1

# 최종 결과를 반환
if r_cnt % 2 == 1:
    arr.reverse()  # 뒤집은 횟수가 홀수일 때 배열을 최종적으로 뒤집음

 

4. 배열이 비어있는 경우, D연산 수행 시

- 초기 배열의 길이가 0이고, D연산이 남아있으면, error을 출력해야한다. 또한, 계속적인 D연산으로 배열이 비어있게 됐을 때도 D연산이 남아있다면 D연산을 수행할 수 없으므로 error를 출력해야한다.

# 초기배열이 비어있는데 D 연산이 있는 경우 에러
if n == 0 and 'D' in p:
    return 0

# 배열에 있는 수를 순서대로 수행
for op in operations:
     # 배열이 비어있는데 D 연산이 있는 경우 에러
    if n == 0 and 'D' in p:
        return 0

 

 

 

문제 리뷰

정수 배열을 선영이가 만든 AC 언어를 이용해 연산하는 문제로, 입력에 대괄호와 쉼표가 포함되는 것을 고려하여 문제를 해결했다. 정수들을 뒤집거나 지우는 과정을 효율적으로 연산하기 위해 덱(Deque) 자료구조를 이용하면 된다고 판단했다 *파이썬의 내장 모듈 collections에 포함된 덱(Deque) 자료구조를 활용했다.

 

덱 (Deque, Double-ended queue)

덱(Deque)은 리스트 양쪽 끝에서의 빠른 삽입과 삭제를 지원하며, 큐(Queue)와 스택(Stack)의 특성을 모두 가진다.

덱(Deque)은  연결 리스트(Linked list)와 비슷한 형태로 구현되어 있어서, 리스트의 양쪽 끝에서의 연산이 O(1)의 시간복잡도로 수행되기 때문에 리스트의 append() 및 pop() 연산보다 효율적이다.

 

장점

- 양쪽 끝에서의 삽입과 삭제가 가능

 

단점

- 메모리 사용량이 큼
 

 

코드 설명

def AC(p, n, arr):
    # 문자열 p를 함수 리스트로 변환
    operations = deque(p.replace('RR', ''))  # 연속해서 두 번 R이 나오면 무시
    r_cnt = 0  # 뒤집기 연산의 횟수를 저장하는 변수
    
    # 초기배열이 비어있는데 D 연산이 있는 경우 에러
    if n == 0 and 'D' in p:
        return 0
    
    # 배열에 있는 수를 순서대로 수행
    for op in operations:
         # 배열이 비어있는데 D 연산이 있는 경우 에러
        if n == 0 and 'D' in p:
            return 0
        # R 연산은 뒤집기, 뒤집은 횟수를 증가
        if op == 'R':
            r_cnt += 1
        # D 연산은 첫 번째 수를 버리기, 뒤집은 횟수에 따라 첫 번째 또는 마지막 수를 제거
        elif op == 'D' and n > 0:
            if r_cnt % 2 == 0:
                arr.popleft()  # 뒤집은 횟수가 짝수일 때는 첫 번째 수를 제거
            else:
                arr.pop()  # 뒤집은 횟수가 홀수일 때는 마지막 수를 제거
            n -= 1

    # 최종 결과를 반환
    if r_cnt % 2 == 1:
        arr.reverse()  # 뒤집은 횟수가 홀수일 때 배열을 최종적으로 뒤집음
    return list(arr)

 

해당 문제를 해결하기 위한  중심 구현 코드이다. 이 코드는 주어진 함수 p에 따라 배열 arr에 수행되는 연산을 구현한 AC함수로. 코드는 R 연산(뒤집기)과 D 연산(첫 번째 수 제거)을 처리하여 최종 결과를 반환한다.

 

먼저 연속해서 나오는 'RR'을 무시하고 함수들을 리스트로 변환하고,  뒤집기 연산의 횟수를 기록하기 위한 변수를 선언한다. 그리고 초기 배열이 비어있는데 D 연산이 포함된 경우에 대한 예외처리 를 수행한다.

주어진 함수들을 순회하면서 연산을 수행할 때, R 연산은 뒤집기이므로 뒤집은 횟수를 증가시킵니다. D'연산은 첫 번째 수를 제거하는데, 뒤집은 횟수에 따라 첫 번째 또는 마지막 수를 제거한다. 연산 중 배열이 비어있는데 D 연산이 있는 경우 0을 반환한다.

뒤집은 횟수가 홀수인 경우, 배열을 최종적으로 뒤집는다.

 

result = AC(p, n, arr)

if result == 0:
    print('error')
else:
    print('[{}]'.format(','.join(map(str, result))))

 

AC함수의 반환 값을 result에 저장하여 반환 값이 0이면 error 출력 아니면, 배열 형식에 맞게 최종 결과 리스트를 출력한다.

 

 

 

전체 코드 

from collections import deque
import sys


def AC(p, n, arr):
    # 문자열 p를 함수 리스트로 변환
    operations = deque(p.replace('RR', ''))  # 연속해서 두 번 R이 나오면 무시
    r_cnt = 0  # 뒤집기 연산의 횟수를 저장하는 변수
    
    # 초기배열이 비어있는데 D 연산이 있는 경우 에러
    if n == 0 and 'D' in p:
        return 0
    
    # 배열에 있는 수를 순서대로 수행
    for op in operations:
         # 배열이 비어있는데 D 연산이 있는 경우 에러
        if n == 0 and 'D' in p:
            return 0
        # R 연산은 뒤집기, 뒤집은 횟수를 증가
        if op == 'R':
            r_cnt += 1
        # D 연산은 첫 번째 수를 버리기, 뒤집은 횟수에 따라 첫 번째 또는 마지막 수를 제거
        elif op == 'D' and n > 0:
            if r_cnt % 2 == 0:
                arr.popleft()  # 뒤집은 횟수가 짝수일 때는 첫 번째 수를 제거
            else:
                arr.pop()  # 뒤집은 횟수가 홀수일 때는 마지막 수를 제거
            n -= 1

    # 최종 결과를 반환
    if r_cnt % 2 == 1:
        arr.reverse()  # 뒤집은 횟수가 홀수일 때 배열을 최종적으로 뒤집음
    return list(arr)


def main():
    T = int(sys.stdin.readline().strip())  # 테스트 케이스의 개수

    for _ in range(T):
        p = sys.stdin.readline().strip()  # 수행할 함수
        n = int(sys.stdin.readline().strip())  # 배열에 들어있는 수의 개수
        # 배열이 비어있을 때
        if n == 0:
            arr = deque(sys.stdin.readline().strip()[1:-1])
        else:
            arr = deque(map(int, sys.stdin.readline().strip()
                        [1:-1].split(',')))  # 배열에 들어있는 정수

        result = AC(p, n, arr)

        if result == 0:
            print('error')
        else:
            print('[{}]'.format(','.join(map(str, result))))


if __name__ == "__main__":
    main()

---

# 처음에 문제를 해결할 때, 무작정 생각없이 문제해결에만 초점을 맞춰서 시간초과도 많이 나고, 반례도 많이 생겨서 쉽지 않았다. 그래도 차근차근 원인을 파악하면서 문제의 조건들을 유리하게 이용하는 방법을 터득한 것 같다. 특히 연산량을 줄이는 방식을 고민해보면서 더 나은 연산을 위한 코드를 작성하게 되었고, 입출력 처리에 대한 예외파악도 중요하다는 것을 알게 되었다.