백준 5430번 AC | python | 단순 구현

문제

링크

풀이

함수의 유형은 배열을 뒤집을 수 있는 R과 배열의 첫째 수를 버리는 D 두 가지이다. 또한 함수는 조합해서 사용 가능하며 이들은 모두 연속적으로 수행되어야한다.

해당 문제는 배열로 파이썬의 리스트 자료형을 사용할 경우 reverse()나 pop(0)를 수행 할 때마다 모두 O(N)의 시간복잡도가 걸리므로 시간초과를 피해갈 수 있는 로직을 설계하는 것이 중요하다는 것이다.

아이디어는 매우 간단한데, 일단 현재 배열의 순서가 뒤집혔는지에 따라 양쪽에서 원소를 버릴 수 있어야하므로 큐를 사용해서 배열을 구성한다.

또한 큐를 사용하면 어느 방향으로 빼든 동일하게 O(1)의 시간이 걸리므로 함수를 수행할 때마다 굳이 실제로 배열을 reverse 해 줄 필요가 없다. 즉, 함수 수행이 모두 끝났을 때 뒤집혔는지 여부를 알면 되며, 이는 flag 변수로 판단한다.

전체 코드는 아래와 같다.
사실 해당 문제는 문제 자체가 어려운 것이 아니라, 입출력하기가 꽤 이상해서 까다로워서 그 점을 유의하면 매우 빠르게 풀이할 수 있을 것이다.

import sys
from collections import deque

input = sys.stdin.readline

t = int(input())


answer = []
for _ in range(t):
    p = input().strip()
    n = int(input().strip())
    arr = list(input().strip()[1:-1].split(","))
    q = deque(arr)
    reverse = 0
    error = 0
    if n == 0:
        q = []

    for i in p:
        if i == "R":
            reverse = not reverse
        else:
            if len(q) < 1:
                answer.append("error")
                error = 1
                break
            else:
                if reverse:
                    q.pop()
                else:
                    q.popleft()

    if not error:
        if reverse:
            q.reverse()
        answer.append("[" + ",".join(q) + "]")

for a in answer:
    print(a)