[ 백준 5430 ] AC - Python

문제 보기

이 문제는 시간 초과를 해결하는 것이 핵심이다.

시간 초과를 해결하기 위해서 아래 2가지를 고려하였다.

 

1. 어떠한 자료구조를 사용할 것인지?

- AC 문제에서는 양쪽에서 출력이 가능해야 하기 때문에 덱을 사용하였다. 덱은 양쪽에서 모두 입력과 출력이 가능한 자료구조이며 파이썬에는 이미 deque로 정의되어 있기 때문에 그대로 사용하면 된다.

 

2. 주어진 연산을 어떤 과정으로 수행할 것인지?

- 주어진 연산이 RR이라고 가정해보자. RR의 수행 결과는 결국 원래 값이 된다. 이 경우에는 연산을 하지 않는 것이 좋다. 따라서 주어진 연산을 순차적으로 실행하는 것이 아니라, 뒤의 상황을 고려하면서 구현하였다.

- 뒤집기(R)의 개수를 파악하고 D 연산을 수행한 후 마지막에 추가적으로 R 연산을 수행하였다.

 

R 연산의 개수를 2로 나눠서 짝수이면 제일 왼쪽 값을 제거하고, 홀수이면 제일 오른쪽 값을 제거하였다.

 

---

코드

from collections import deque
import sys


if __name__ == "__main__":
    T = int(sys.stdin.readline())

    for _ in range(T):
        operation = input()
        n = int(sys.stdin.readline())
        temp = input()
        temp = temp[1:-1]  # [ ] 제거

        if "," not in temp and temp != "":
            num_deque = deque([int(temp)])
        elif temp != "":
            num_deque = deque(map(int, temp.split(",")))
        else:
            num_deque = deque()

        # 명령 수행
        flag = 1
        cnt = 0  # Reverse의 개수

        for i in range(len(operation)):
            if operation[i] == "R":
                cnt += 1
            else:
                if len(num_deque) == 0:
                    flag = 0
                    break

                if cnt % 2 == 0:
                    num_deque.popleft()
                else:
                    num_deque.pop()
        if cnt % 2 == 1:
            num_deque.reverse()

        if flag:
            print("[", end="")
            for i in range(len(num_deque)):
                if i == len(num_deque) - 1:
                    print(num_deque[i], end="")
                else:
                    print(str(num_deque[i]) + ",", end="")
            print("]")
        else:
            print("error")