[알고리즘] 백준 5430 파이썬 - AC

 

5430번: AC

 

문제

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

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

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

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

 

문제풀이

from collections import deque
import sys
input = sys.stdin.readline
for i in range(int(input())):
    try:
        p = input()
        n = int(input())
        x = input().rstrip()[1:-1].split(",")
        queue = deque(x)
        cnt=0
        if n==0:
            queue=[]
        for j in p:
            if(j=="R"):
                cnt+=1
            elif(j=="D"):
                if(len(queue)==0):
                    raise ValueError
                else:
                    if cnt%2==0:
                        queue.popleft()
                    else:
                        queue.pop()
        if cnt %2==0:
            print("["+",".join(queue)+"]")
        else:
            queue.reverse()
            print("["+",".join(queue)+"]") 
    except:
        print("error")

- deque를 사용한 이유:

보통 큐(queue)는 선입선출(FIFO) 방식으로 작동한다. 반면, 양방향 큐가 있는데 그것이 바로 데크(deque)다.

즉, 앞, 뒤 양쪽 방향에서 요소(element)를 추가하거나 제거할 수 있다.

데크는 양 끝 요소의 append와 pop이 압도적으로 빠르다.

컨테이너(container)의 양끝 요소(element)에 접근하여 삽입 또는 제거를 할 경우, 

리스트(list)가 이러한 연산에 O(n)이 소요되는 데 반해, 데크(deque)는 O(1)로 접근 가능하다.

즉 쉽게 말해, 시간 복잡도가 낮고 앞과 뒤 양쪽 방향에서 요소를 추가, 제거할 수 있기에 사용했다.

코드설명

- D를 만났을 때 그 전의 R이 나온 횟수를 짝수와 홀수로 나누어서 각각 앞과 뒤에서 값을 제거해준다.

  즉 reverse 함수를 계속해서 사용하지 않아 시간 복잡도를 줄일 수 있다.

- 이후 총 R이 나온 횟수에 따라 출력 전에 queue를 reverse할지 안 할지를 결정한다.

  최종적으로 join을 사용하여서 문제에서 원하는 양식으로 맞추어준다.

 

- 추가로 문제 풀이 중 실제 에러가 발생하면 except문으로 가서 "error"를 출력하게 한다.