[자료구조/큐] 백준 5430 AC - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

5430번: AC

 

 

 

2. 문제 풀이

1) R: 정수배열 뒤집기
2) D: 첫 번째 수 버리기 (단, 빈 배열이면 Error)

 

 두 연산을 수행하는 자료구조를 만들어야 합니다. 배열의 크기가 최대 100000이고, R연산이 최대 100000번 일어날 수 있습니다. 따라서 R연산마다 배열을 뒤집으면 시간 초과가 납니다.

 

2022.02.10 - [Algorithm] - [Algorithm] 큐(Queue), 선입선출 줄서기 자료구조

[Algorithm] 큐(Queue), 선입선출 줄서기 자료구조

 내부 연산은 없고, 첫 번째 수만 뽑으면 됩니다. 따라서 나오는 입구만 R연산에 따라 앞뒤로 바꾸면 됩니다.

 파이썬의 deque 자료구조를 활용하면, 맨 앞과 맨 뒤의 수를 쉽게 제거할 수 있습니다.

 

 

 

3. 코드

from collections import deque
import sys
input = sys.stdin.readline

#입력
T = int(input())
for _ in range(T):
    p = input().rstrip()
    n = int(input())
    if n == 0:
        input()
        numlist = deque([])
    else:
        numlist = deque(list(input().strip("[]\n").split(",")))

 정수배열을 deque에 입력받습니다. 입력형식이 [1,2,3,4] 이므로, 불필요한 대괄호는 제거하고 콤마로 구분합니다.

 n이 0인 경우는 따로 빈 큐를 만들어줍니다. 만약 위 방식대로 []을 입력받는다면, deque([''])로 빈 스트링이 있게 됩니다.

 

 

    #연산시작
    front = True #앞에서부터 제거
    for op in p:
        # 뒤집기
        if op =='R':
            #Toggle
            if front:
                front = False
            else:
                front = True
        # 버리기
        else:
            #빈 리스트가 아님
            if numlist:
                #앞에서부터 꺼내기
                if front:
                    numlist.popleft()
                #뒤에서부터 꺼내기
                else:
                    numlist.pop()
            #빈 배열임
            else:
                print("error")
                break

 R 연산이 있을때마다 front 변수를 전환해줍니다. 앞이었다면 뒤부터, 뒤였다면 앞부터 숫자를 제거합니다.

 

 

    #error없이 모든 연산을 마침
    else:
        if front:
            #앞쪽으로 모든 배열 꺼내기
            lst = ",".join(list(numlist))

        else:
            #뒤쪽으로 모든 배열 꺼내기
            lst = ",".join(list(numlist)[::-1])
        print(f"[{lst}]")

 for-else구문을 사용해서, error없이 모든 연산을 마쳤다면 정수배열을 출력합니다. join함수를 사용해서 리스트를 ','로 구분해서 문자열로 변환합니다.