[백준 5430] - AC(Gold V)

📒문제

🎈풀이

import sys
from collections import deque

T = int(sys.stdin.readline().rstrip())

for _ in range(T):
  J = True #True = popleft, False = pop
  err = False

  F = list(map(str, sys.stdin.readline().rstrip()))
  N = int(sys.stdin.readline().rstrip())
  T = sys.stdin.readline().rstrip()

  T = T[1:-1]
  
  if N != 0: arr = deque(map(int, T.split(",")))
  else: arr = []

  for i in range(len(F)):
    if F[i] == 'R':
      J = not J
    elif F[i] == 'D':
      if not arr:
        print("error")
        err = True
        break
      if J:
        arr.popleft()
      elif not J:
        arr.pop()
  
  if err: continue

  result = "["
  if arr and J:
    for i in range(len(arr)):
      result += str(arr[i])
      if i != len(arr)-1: result += ","
      
  
  elif arr and not J:
    for i in range(len(arr)-1, -1, -1):
      result += str(arr[i])
      if i != 0: result += ","
  result += "]"

  print(result)

이 문제는
1. 덱(deque)을 써야 시간 복잡도에 걸리지 않는다는 것,
2. 그리고 실제 reverse연산을 하지 않고 reverse flag를 써주면서 flag에 따라 앞 뒤 요소를 빼주는 게
핵심인 문제였다.

덱을 쓰지 않고 그냥 list를 쓰면서 시간복잡도가 O(N)인 연산 reverse나 pop을 쓸 경우, 함수 p의 길이가 최대 100000일 때 반복횟수가 최대 천만번일 경우 1초라는 시간 제한을 통과할 수 없다.

그 이외에 문자열 파싱이나 예외 케이스 처리 같은 자잘한 경우를 잘 생각해주어야 하는 문제였다.