[Algorithm] 백준 5430번: AC | 덱 응용

문제 출처: https://www.acmicpc.net/problem/5430

---

1. 결과

메모리 46428KB, 시간 336ms

2. 풀이

이 문제는 우선 입력과 출력 예시를 통해 확인할 수 있겠지만, 예시처럼 입력을 받아서 원하는 형태의 숫자로 변환하는 것, 출력을 원하는 형식대로 출력하는 것이 생각보다 고민이 됐다. 그래서 아래 코드처럼 입력과 출력이 조금은 더 길다.

본격적인 문제의 아이디어는 결국 뒤집든 안 뒤집든 한쪽 끝에서 숫자를 제거한다는 점에서 떠올렸다. 만약 스택의 형태로 풀었다면, D일 때는 [1:]로 슬라이싱을, R일 때는 reverse 정렬을 하게 되는데, 이는 슬라이싱을 할 때마다 남은 길이만큼 연산(한 칸씩 앞으로 당기는 것)이 발생하고, R이 있을 때마다 정렬이 발생한다는 뜻이다. 반대로 큐를 통해 푼다면, R이 이전에 홀수만큼 발생했다면 결국 원래의 배열에서 뒤집힌 상태이므로 원래 배열의 뒤에서 제거,  R이 0을 포함해서 짝수만큼 발생했다면  원래 배열과 같은 상태이므로 원래 배열의 앞에서 제거하면 되는 것이다. 이것은 파이썬의 내장 라이브러리 collections의 deque를 통해 쉽게 구현할 수 있다.

원래 배열을 deque에 넣고 R이 발생한 횟수에 따라 1씩 누적하면서, 만약 D가 나왔을 때 R이 홀수라면 pop, R이 짝수라면 popleft을 진행하면 되는 것이다. 단, 처음부터 배열에 아무것도 없는데 명령에 D가 있는 경우, deque가 남아있지 않은 상태에서 D가 나오는 경우는 'error'를 출력하도록 한다. 그리고 마지막에 누적된 R이 홀수라면 마지막 배열을 한 번 뒤집어서 정렬한 후 출력하면 된다. 이를 구현한 코드는 아래와 같다.

이 방법은 주어진 문제에서 deque를 이용해 정렬을 단 한 번만 발생할 수 있도록 구현한 방법이다. 문제의 분류가 큐에 있기 때문에 이렇게 풀이를 했는데, 명령어에 따라 제거된 후 남은 앞뒤 인덱스를 저장하는 변수를 생성해서 전체 명령어에 따라 남은 인덱스만큼만 배열에서 추출하고 출력하는 방법은 어떨까 싶다.

import sys
from collections import deque

def AC(string_num, command, n):
    q = deque(map(int, string_num))
    reverseCnt = 0
    
    for c in command:
        if c == 'R': reverseCnt += 1
        elif c == "D":
            if not q: return 'error'
            if reverseCnt % 2 == 0: q.popleft()
            else: q.pop()
    
    if reverseCnt % 2 == 1: q.reverse()
    return "[" + ','.join(map(str, q)) + "]" 

def main():
    T = int(sys.stdin.readline())
    for _ in range(T):
        command = sys.stdin.readline().strip()
        N = int(sys.stdin.readline())
        nums_str = sys.stdin.readline().strip()[1:-1].split(',')
        if N == 0 and 'D' in command: print('error')
        else: print(AC(nums_str, command, N)) if N != 0 else print('[]')
    return

if __name__ == "__main__":
    main()