[구현] 백준 5430_AC

https://www.acmicpc.net/problem/5430

5430번: AC

선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다.

함수 R은 배열에 있는 수의 순서를 뒤집는 함수이고, D는 첫 번째 수를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다.

함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. 예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 수를 버리는 함수이다.

배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하시오.

---

시간초과 코드

 

# 백준 [구현] 5430_AC
import sys
input = sys.stdin.readline

t = int(input())

for i in range(t):
  cases = input().strip()
  n = int(input())
  list_str = input().strip() 
  lists = list_str.replace('[','').replace(']','').split(',')
  
  for i in range(len(cases)):
    if cases[i] == 'R':
      lists.reverse()
    elif cases[i] == 'D':
      if len(lists) >= 1:
        del lists[0]

  if len(lists)>0:
    print('['+','.join(lists)+']')
  else:
    print("error")

시간 초과가 나는데에는 리스트 reverse 함수의 공이 큽니다

이를 방지하기 위해 deque를 사용했습니다.

맞은 코드

# 백준 [구현] 5430_AC
import sys
from collections import deque
input = sys.stdin.readline

t = int(input())

for i in range(t):
  cases = input().rstrip() #개행 문자(\n)을 없애기 위함
  n = int(input())
  queue = deque(input().rstrip()[1:-1].split(',')) #개행 문자(\n)을 없앤 후, 입력값 양 쪽의 [,]을 없앰. 그 후 ,단위로 나눠 deque에 담음 

  flag = 0 #R명령어가 몇 번 수행되었는지를 저장하는 변수 (reverse를 줄이기 위함!)

  if n==0: #큐의 초기상태가 빈 큐인 경우를 고려함.
    queue = [] #이유: 입력으로 받은 큐가 []면, 빈 문자열 ''를 하나의 원소로 가져서 len(queue)가 1이 나옴. 그래서 아래 if len(queue) == 0: 문에 걸리지 않아 error를 발생시키지 못함. 따라서 빈 큐로 만듦.
  
  for c in cases:
    if c == 'R':
      flag+=1
    elif c == 'D':
      if len(queue) == 0:#큐가 비어있을 때
        print("error")
        break
      else: #큐가 비어있지 않을 때
        if flag%2 == 0: #R 수행횟수가 짝수면, 원상태와 똑같으므로 맨 앞 원소 삭제
          queue.popleft()
        else: #R 수행횟수가 홀수면, 뒤집어진 상태이므로 맨 뒤 원소 삭제 
          queue.pop() #굳이 반복문을 돌 때마다 reverse하지 않아도 됨! 시간 초과 문제 해결! => 리스트가 아닌 덱을 써야하는 이유!(덱은 양쪽에서 삽입과 삭제가 가능한 자료구조이므로 굳이 리스트의 원소를 재배치하지 않아도 앞뒤로 삭제 가능!)
  else:
    if flag%2==1: #R 수행횟수가 홀수면
      queue.reverse() #뒤집음 (단 한번이기 때문에 시간초과 안 남.)
    print('['+','.join(queue)+']') #최종 상태 출력

주석으로 자세히 설명해두었으니 참고 부탁드립니다!