백준 5430 AC(Queue)

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

5430번: AC

문제는 간단하다. 주어진 배열에서 R이면 reverse(), D면 pop()을 시키면 되는 문제였다.

 

주요 요점은 어떤 자료구조를 사용하냐는 건데 함수p와 n의 범위가 100,000이기 때문에

list로 접근하면 안된다는걸 바로 알아차렸다.

따라서 queue로 접근하면 pop에 대한 시간복잡도는 O(1)이기 때문에 queue()로 선택했다.

 

여기서 가장 시간을 많이 잡아먹는 연산은 당연히 reverse()이다.

그래서 R을 만날때마다 reverse()를 하지말고 RR이 만나면 없던일처럼 되니까 RR만 고려를 해줬더니 시간초과가 났다.

 

생각해보니까 RDRD이런형식이면 reverse()을 계속 해줘야되기 때문에 비효율적이라는걸 알았다.

queue는 left, right 모두 pop이 가능한 자료구조이고 만약 R이 홀수만큼 나왔다면 reverse()를 시켰을테니까 queue.pop(), 짝수면 queue.popleft() 이런 방식으로 생각했다.

from collections import deque
import sys


t = int(input())
for _ in range(t):
    data = sys.stdin.readline().rstrip()
    n = int(input())
    arr = deque(sys.stdin.readline().rstrip()[1:-1].split(','))
    
    if n == 0:
        arr = deque()

    R_cnt = 0

    for i in data:
        if i == 'R':
            R_cnt += 1
        elif i == 'D':
            try:
                if R_cnt % 2:
                    arr.pop()
                else:
                    arr.popleft()
            except:
                print('error')
                break
    else:
        if R_cnt % 2:
            arr.reverse()
            print('[' + ','.join(arr) + ']')
        else:
            print('[' + ','.join(arr) + ']')

 

 

p.s : 출력결과 형식을 맞추기위한 문자열 다루기가 좀 부족한 것 같음. join() 활용을 잘해보자