덱 - 문제 후기

AC GOT ME LIKE...

덱 (Deque)

---

덱 (deque)의 구조

덱은 Deque(Double Ended Queue)로 근본적으로는 queue와 그 구조를 상당수 공유하지만, 단 한 가지가 다르다면, 이름에서도 알 수 있듯이, queue의 양쪽에서 접근이 가능하다. 기존 queue는 FIFO(First In First Out)의 속성을 가졌다면, deque는 그러한 규칙 없이 양쪽에서 pop, push가 매우 자유롭기 때문에 아주 편리하다.

 

구현이 복잡하다고 하는데 파이썬에서는 다 구현을 해주니까, 안 쓸 이유가 전혀 없고, pop, push의 시간 복잡도도 O(1)로써 빠르니까 아주 편리한 자료구조라고 생각이 든다. 리스트의 랜덤 요소에 접근 (양 끝이 아닌 아무 값) 해야 할 때 말고는 자료구조 후보군에 항상 있을 것 같으며, 앞 뒤에서 삽입, 삭제가 자주 일어나거나, 데이터의 개수가 가변적일 때 아주 유용할 거 같다.

 

(BOJ 5430) AC

---

 

5430번: AC

위의 사진에서 보다시피, 덱에서는 3개의 문제가 주어졌는데, 덱과 회전하는 큐 문제는 그닥 어렵지는 않았지만, 골드 5의 난이도를 가진 AC가 살짝 까다로웠기 때문에 후기를 남길 문제로 선정하였다.

 

이 문제를 간단하게 요약하자면, R(Rotate), D(Delete) 로 이루어진 명령어, 예를 들어 "RDD" -> 한번 뒤집고 앞에서부터 순서대로 2번 삭제해, 를 받고 수열을 넣으면 명령어대로 연산이 이루어지고 그 결과를 출력하는 문제이다. (핵심만 요약, 이해 안 되면 위의 링크로)

 

내가 이 문제를 풀면서 느꼈던 핵심 포인트는 바로,

1. 입력을 숫자로만 받는게 아니고 [ ] , 기호들도 포함해서 입력받고 그에 따라 출력하는 것, 이게 왜 포인트였냐면, 바로 deque를 선언해서 사용하면, 출력할 때 deque [         ] 이런 식으로 같이 출력이 되어서 우리가 원하는 것만 출력이 온전히 안된다. 아주 사소한 issue이지만 deque를 파이썬에서 처음 사용해보았기 때문에, 살짝 까다로웠다 ( PS를 너무 오래 쉬어서 까먹어서 그렇기도 하다...)

 

2. 그리고 알고리즘 적으로 가장 중요했던 Rotate의 Flag. 이 문제의 핵심인데, 그 이유는 예를 들어, 명령어가 RRRRRRRRR 이었다고 가정하면 Rotate를 9번 해야 하는 것인데, O(N)의 시간 복잡도를 가진 deque.reverse()를 9번 반복하는 것은 필히 시간 초과 에러를 발생시키기 때문에 다른 방법을 찾아야 한다.

 

코드와 풀이

---

 #입력
 array = sys.stdin.readline().rstrip()[1:-1].split(',') 
 # 대괄호와 , 를 빼고 리스트에 넣기위한 코드
 
 #출력
   print("[", end='') # 개행을 없애기 위해 end = ''를 넣는다.
        for i in range(len(array)):
            if i == len(array)-1:
                print(str(array[i]),end='') # 동일
            else:
                print(array[i],end=',') # 동일
        print("]")

1. 위의 코드는 전체 코드 중에 입력부와 출력부만 가져온 것이다. 입력부에는 개행을 없애는 rstrip(), 양 끝의 대괄호를 없애기 위한 [1:-1], 그리고 콤마를 기준으로 수열을 나누어주는 split(', ')을 사용하여 숫자만 입력을 받았다.

 

그리고 입력부에서 숫자만을 다뤄서 연산을 한뒤에 출력할 때에는 다시 [ a, b , c... ]의 형식으로 출력해주어야 하기 때문에, print("[", end = ' ' )를 통해 대괄호를 처음에 넣어주고 이렇게 print를 따로 해줄 경우에는 자동으로 개행이 들어가기 때문에 개행을 없애줄 end = ' '를 이용하여 출력이 연속되도록 해준다.

 

R, D 연산부 알고리즘

2. RRRRRRR과 같은 다중 reverse 명령이 왔을 때 시간초과에 안 걸리기 위해서 flag 개념을 사용하였다. 그리고 좀 더 나아가서, 잘 생각해보면 reverse를 하고 삭제를 하는 상황은, reverse를 거치지 않은 리스트의 마지막 원소를 삭제하는 것과 동일하고, 몇 번의 R이 있었는가를 count 하여 짝수이면 그대로 출력하고, 홀수 이면, 거꾸로 뒤집어서 출력하면 동일하다는 개념을 이용하여 시간 초과 에러를 피할 수 있었다. 

 

아래는 전체 코드이다.

 

import sys
from collections import deque
case_num = int(sys.stdin.readline())
reverse_flag = True
error_flag = False
count = 0
for _ in range(case_num):
    command = list(sys.stdin.readline().rstrip())
    length = int(sys.stdin.readline()) 
    array = sys.stdin.readline().rstrip()[1:-1].split(',')
    array = deque(array)
    for i in command:
        if i == 'R':
            if not array :
                error_flag = True
            elif reverse_flag == True:
                reverse_flag = False
            else:
                reverse_flag = True
            count += 1
        elif i == 'D':
            if not array or length == 0:
                error_flag = True
            elif reverse_flag == True:
                array.popleft()
            else:
                array.pop()

    if error_flag == True:
        print("error")
    
    else:    
        if count % 2 != 0: 
            array.reverse()
        print("[", end='') # 개행을 없애기 위해 end = ''를 넣는 것
        for i in range(len(array)):
            if i == len(array)-1:
                print(str(array[i]),end='')
            else:
                print(array[i],end=',')
        print("]")
    
    reverse_flag = True  # flag 초기화
    error_flag = False 
    count = 0
    

 마무리

---

6월 18일부로 네패스 인턴이 끝나고 1주일만 쉰다고 게으르게 놀았더니 정신상태가 살짝 게을러지고, 코드를 짜는데도 집중이 잘 안되었지만, 백준 문제를 맞추면 나오는 "맞았습니다!!"를 보니까 또 살짝 흥미와 집중력이 생기는 기분이다. deque는 어려운 개념이 아니라 빨리 넘어가고, 뒤에 나오는 BFS, DFS도 빨리 풀고, 이것저것 빨리 끝내서 8월 초에는 산업체 지원원서를 낼 수 있는 레벨이 될 수 있기를 소망한다.