[백준] 5430번: AC (Python)

문제는 어렵지 않으나, 입출력을 약간 번거로운 편인 문제.

 

import sys
from collections import deque

for test_case in range(int(sys.stdin.readline())):
  error = False

  command_list = sys.stdin.readline().strip()
  num_cnt = int(sys.stdin.readline())
  num_list = deque(sys.stdin.readline().strip()[1:-1].split(","))
  
  if num_cnt == 0:
    num_list = deque()

  for command in command_list:
    if command == "R":
      num_list.reverse()
    else: 
      if num_list:
        num_list.popleft()
      else:
        error = True
        break
      
  if error:
    print("error")
  else:
    print("["+",".join(num_list)+"]")

다음과 같이 코드를 작성했으나, 시간초과 발생.
list를 deque로 변경하고 다시 제출했으나, 여전히 시간초과가 발생했다.
원인을 찾아보니 num_list가 굉장히 길다보니, reverse()를 수행하는 시간이 상당히 걸리는 것으로 보인다.
reverse()를 최대한 사용하지 않도록 코드를 수정했다.

import sys
from collections import deque

for test_case in range(int(sys.stdin.readline())):
  error = False
  reverse = False

  command_list = sys.stdin.readline().strip()
  num_cnt = int(sys.stdin.readline())
  num_list = deque(sys.stdin.readline().strip()[1:-1].split(","))
  
  if num_cnt == 0:
    num_list = deque()

  for command in command_list:
    if command == "R":
      if reverse:
        reverse = False
      else:
        reverse = True

    else: 
      if num_list:
        if reverse:
          num_list.pop()
        else:
          num_list.popleft()
      else:
        error = True
        break
      
  if error:
    print("error")
  elif reverse:
    num_list.reverse()
    print("["+",".join(num_list)+"]")
  else:
    print("["+",".join(num_list)+"]")

 

 

keypoint

• list 대신 deque() 사용하기
• 직접 reverse() 대신 변수로 reverse 상태인지 기억하기