[BaekJoon] 2346번 풍선 터뜨리기 (Python) 문제 풀이 [Silver 3]

문제

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

 

어떻게 풀 것인가?

덱(Deque) 자료구조를 활용하는 문제입니다.

풍선이 원형으로 배치되어 있고, 터뜨린 풍선의 종이값만큼 이동해야 하므로 덱의 rotate를 활용하면 원형 이동을 간단하게 구현할 수 있습니다.

덱에 (풍선 번호, 종이값)을 넣어두고, 매번 popleft()로 현재 풍선을 터뜨립니다. 그 다음 종이값에 따라 회전시키는데, 양수면 오른쪽으로 이동해야 하므로 rotate(-(val-1)), 음수면 왼쪽으로 이동해야 하므로 rotate(-val)을 해줍니다. popleft()로 이미 한 칸 이동한 상태이기 때문에 양수일 때 1을 빼주는 것이 포인트입니다.

 

코드

import sys
from collections import deque

input = sys.stdin.readline

N = int(input())
numbers = list(map(int, input().split()))

dq = deque()
for i in range(N):
    dq.append((i + 1, numbers[i]))  # (번호, 종이값)

result = []
while dq:
    num, val = dq.popleft()  # 현재 풍선 터뜨리기
    result.append(num)
    if not dq:
        break
    if val > 0:
        dq.rotate(-(val - 1))  # 오른쪽으로 val칸 → 왼쪽으로 val-1 회전
    else:
        dq.rotate(-val)        # 왼쪽으로 |val|칸 → 오른쪽으로 |val| 회전

print(*result)