함수의 유형은 배열을 뒤집을 수 있는 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)