[백준 알고리즘: python 3] #5430 - AC (큐/덱 스터디)

이번 포스트는 큐/덱 문제 중, 5430번 AC 문제를 풀기로 했습니다. 알고리즘 스터디에서 선정한 문제에요!

---

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

 

큐(Queue)와 덱(Deque, Double-ended Queue의 약자)은 스택(Stack)과 같이 알고리즘 풀이에 많이 활용되는 자료 구조입니다. 덱은 이름에서 알 수 있듯이 큐의 한 종류입니다. 스택과 큐의 차이점은 스택은 정보를 넣고 뺄 수 있는 입구가 하나임과 다르게 큐는 입구가 두 개라는 것입니다. 그 중, 큐는 정보가 들어가고 나가는 방향이 결정이 되어 있고 덱은 결정이 되어 있지 않고 입구 양쪽에서 넣거나 뺄 수 있습니다. 아래 그림을 참고해주세요!

스택/큐/덱 구조의 그림 (출처: https://ehclub.co.kr/1222)

 

Hint!

5430번 AC 문제는 Deque 자료 구조를 활용하는 문제입니다. 양 쪽에서 정보의 입력과 삭제가 가능한 구조를 활용해야 하죠. 먼저, AC라는 언어에는 수열을 뒤집는 R, 수열의 첫번째 숫자를 삭제하는 D라는 두 함수가 존재한다고 소개가 되어있습니다. 이 문제에서는 R이라는 함수를 잘 해석하는 것이 중요해요. 수열을 뒤집는다라.. 아마 함정이죠. 문제에서 시키는대로 수열을 코드를 통해 뒤집어 버리면 시간초과가 나고 말겁니다. 덱이라는 자료 구조를 생각해보면, 수열을 뒤집을 필요가 없이 R은 다음 D가 나올 경우 어느 입구(전방, 후방)에서 숫자를 삭제해야 하는지 결정하는 요소로만 여기면 됩니다. 즉, 수열을 뒤집지 말고 어디서 숫자를 빼면 되는지 정도의 정보만 변경을 하면됩니다. 

 

풀이를 통해 설명을 하면,

1. 입력 받은 수열은 num_list, 함수 셋은 p라고 부르겠습니다.
2. 먼저 p 안의 R과 D의 개수를 세야 합니다. R의 개수는 최종적으로 출력할 수열이 정방향인지, 역방향인지 결정합니다. 홀수 일경우 아래 과정을 모두 거치고 수열을 뒤집어서 출력하면 됩니다. D의 개수는 AC가 오류를 내는지 확인하는데 사용됩니다. D의 개수가 num_list의 길이보다 크다면 함수를 실행하다가 반드시 오류를 낼겁니다. 빼내야 하는 수의 개수가 존재하는 수보다 많으니까요. 이 경우에는 함수를 중단하고 error를 출력하면 됩니다.
3. 방향을 가리키는 direction이라는 변수를 만들고 처음엔 앞쪽을 의미하게 합니다. 저는 0으로 초기화했어요. 리스트에서 맨 앞 요소의 index는 0이니까요.
4. 입력 받은 함수 셋 p를 차례로 순회합니다.
   1. R을 만났을 때, direction이 0이면 -1로 바꾸고, -1이면 0으로 바꿉니다. 리스트에서 맨 뒤 요소의 index는 -1이니까 삭제할 요소의 위치를 변경한다고 볼 수 있습니다.
   2. D를 만나면 num_list[direction] 위치의 요소를 삭제합니다.
5. R의 개수가 홀수면 최종적으로 만들어진 수열을 뒤집어서 반환합니다. 그렇지 않으면 그냥 반환합니다.

주의!

python으로 이 문제를 풀 때 한 가지 어려울 수 있는 점은, 수열을 입력 받을 때 이게 리스트가 아니라 문자열의 형태로 입력된다는 점입니다. 이 경우, 대괄호를 삭제하고 콤마로 스플릿 하고... 하는 것보단, json 모듈을 import 하셔서 json을 loads 하는 방식으로 코드를 더 깔끔히 할 수 있습니다. 아래 코드에서 확인해 주세요! 물론 출력할 때도, 문제의 예제에서 처럼 리스트 그대로 출력하면 안되고 리스트를 문자열로 변경한 뒤, 공백을 모두 삭제해 주셔야 할 것 같아요! 알고리즘 문제에서는 이런 디테일도 중요한 것 같습니다.

 

아래의 코드로 해결했습니다.

import sys
import json

def AC(p, n, deque):
    # D의 개수가 수의 개수보다 많으면 에러
    if p.count("D") > n: return "error"
    # 수열을 최종으로 뒤집어야 하는지 여부 확인
    if p.count("R") % 2 == 0: final_reverse = False
    else: final_reverse = True
    
    # 수를 빼낼 방향 결정
    direction = 0
    for f in p:
        # R을 만나면 방향 변경
        if f == "R":
            if direction == 0: direction = -1
            else: direction = 0
        # D를 만나면 방향에 해당하는 수를 빼냄
        else: deque.pop(direction)
    
    # 최종으로 뒤집어야하면 뒤집음
    if final_reverse: deque.reverse()

    deque = str(deque).replace(" ", "")
    return deque

T = int(sys.stdin.readline())
results = []
for _ in range(T):
    p = list(sys.stdin.readline().replace('\n', ''))
    n = int(sys.stdin.readline())
    
    # 리스트 형태로 바로 입력받는게 아니라 str 형식으로 입력받게 됨.
    # 이걸 리스트로 바꿔야하는데 가장 간단한 방법은 json 형식으로 읽는 것이라고 판단.
    deque = json.loads(sys.stdin.readline().replace('\n', ''))
    results.append(AC(p, n, deque))

for result in results:
    sys.stdout.write(str(result)+'\n')