[백준][16단계 스택, 큐, 덱 1] 2346번 /풍선 터뜨리기 (파이썬/Python)

1. 문제 설명

2. 코드

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

N = int(input().strip())
moves = list(map(int,input().split()))
dq = deque((i+1,moves[i]) for i in range(N)) #(풍선번호,이동값)
order = []

while dq:
    idx, k = dq.popleft()
    order.append(idx)
    if not dq:
        break
    if k > 0:
        dq.rotate(-(k-1))
    else:
        dq.rotate(-k)
print(*order)

3. 풀이 과정

원형으로 놓여진 풍선들을 원하는 숫자만큼 이동시켜 터트리고 그 수를 저장하면 된다.

이동은 rotate() 함수, 터트리는 건 popleft() 함수, 저장은 따로 빈 리스트를 만들어 append() 함수를 사용한다.

deque 패키지에는 괄호로 묶어주면 묶어준 대로 값이 저장된다.

풍선번호와 이동값을 저장하기 위해 인덱스로 받아서 dq에 저장한다.

dq가 빌 때까지 맨 앞 값을 제거 popleft()하고 그 값을 idx,k로 저장한다.

풍선번호 idx는 order에 저장 append()하고

이동값 k가 양수이면 앞서 제거한 1칸을 빼고 반대 부호로 전환해서 이동 rotate()하고 음수이면 반대 부호 전환만 해서 이동한다.

dq에 값이 없으면 order를 공백 구분해서 출력하기 위해 언패킹 연산자를 붙여 출력한다.

4. 자투리 개념

1. 스택 (Stack)

• 정의 : 데이터를 한쪽 끝(top)에서만 넣고(push) 꺼내(pop)는 구조
• 특징 : 후입선출(LIFO)
• 비유 : 접시 더미
• 대표 연산
  - push(x), pop(), peek()

2. 큐 (Queue)

• 정의 : 데이터를 한쪽 끝(rear)에서 넣고, 반대쪽 끝(front)에서 꺼내는 구조
• 특징 : 선입선출(FIFO)
• 비유 : 줄 서기
• 대표 연산
  - enqueue(x), dequeue(), front()

3. 덱 (Deque, Double-Ended Queue)

• 정의 : 양쪽 끝(front, rear)에서 모두 삽입과 삭제가 가능한 구조
• 특징 : 스텍과 큐의 성격을 모두 가짐
• 비유 : 양쪽에서 들어오고 나갈 수 있는 출입구가 있는 줄
• 대표 연산
  - append(x), appendleft(x), pop(), popleft()

4. * 언패킹(unpacking) 연산자

• 리스트나 튜플을 낱개 인자처럼 풀어주는 역할