[알고리즘] 큐, 덱 - 백준 5430번 AC

정답코드

import sys
from collections import deque

input = sys.stdin.readline
N = int(input())

def solution():
  command = input()
  command = command.replace('RR', '')
  l = int(input())
  arr = input()[1:-2].split(',')

  r, f, b = 0, 0, 0

  for i in range(len(command)):
    if command[i] == 'R':
      r += 1
    elif command[i] == 'D':
      if r % 2 == 0:
        f += 1
      else:
        b += 1
  
  if f + b <= l:
    arr = arr[f:l-b]
    if r % 2 == 0:
      return '[' + ','.join(arr) + ']'
    else:
      return '[' + ','.join(arr[::-1]) + ']'
  else:
    return 'error'


for _ in range(N):
  print(solution())

풀이과정

처음에 이 문제에 접근했던 방법은 배열을 돌면서 R이 나올 때마다 뒤집고 D가 나올 때마다 삭제했었다. 하지만, 이 방법은 시간 효율성이 매우 떨어진다.

배열의 갯수가 100,000개 까지 가능하기 때문에 매 순간 적용하는 것은 비효율적이다.

첫째, 'RR'은 두 번의 뒤집기로 결국 뒤집지 않은 것과 같다.
아래의 코드를 쓰지 않으면 1000KB 정도의 메모리가 더 소모된다.
command = command.replace('RR', '')

둘째, 각 반복문 안에서 뒤집는 경우와 삭제하는 경우의 갯수를 센다. 만약 어떤 반복문 안에서 D를 만났을 때, R의 갯수가 2의 배수이면 RR과 같아져 앞에서 삭제되고 그 반대는 뒤에서 삭제된다.

이렇게 문제를 접근하면 시간 초과를 피할 수 있다.