[Baekjoon] 2346 - 풍선 터뜨리기 (Python)

문제

[BaekJoon] 2346 풍선 터뜨리기

1부터 N개의 풍선이 원형으로 놓여있다.

i번째 풍선의 오른쪽이 i+1번째 / i번째 풍선의 왼쪽이 i-1번째이다.

각 풍선에는 종이가 들어있고 종이의 숫자 paper 는 -N <= paper <= N 이다.

1번(맨앞) 풍선을 터뜨린 뒤 종이에 적혀이는 숫자만큼 이동하여 다음 풍선을 터뜨린다.

종이의 숫자가 양수면 오른쪽, 음수면 왼쪽으로 이동한다.

Input

Input은 풍선 갯수와, N개의 풍선 안의 종이에 적혀있는 숫자이다.

Output

Output은 터진 풍선의 번호가 순서대로 출력되어야한다.

풀이

풍선이 원형으로 놓여있고 rotate를 쓰기 좋은 문제이기 때문에 deque를 사용하였다.

종이 숫자 paper와 풍선의 번호 ballon_idx가 같이 움직여야한다.

deque의 맨 앞 풍선부터 터뜨리고 종이에 적힌 숫자만큼 양수면 오른쪽, 음수면 왼쪽으로 이동한다.

deque.rotate(-) 는 왼쪽으로 회전하기 때문에 종이숫자가 양수일 때의 오른쪽 이동을 담당하고,

deque.rotate(+)는 오른쪽으로 회전하기 때문에 종이숫자가 음수일 때의 왼쪽이동을 담당하면 된다.

ballon_idx.rotate(-i+1) 여기에 +1을 한 이유는, 전에 맨 앞 풍선을 popleft() 해주어 이미 왼쪽으로 1칸씩 회전된 상태이기 때문이다.

Code

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

n = int(input())

paper = deque(list(map(int, input().rstrip().split()))) # 종이 숫자
ballon_idx = deque([i for i in range(1, n+1)]) # 풍선 번호

while paper:
    i = paper[0]
    if i > 0:
        paper.popleft()
        paper.rotate(-i + 1)
        print(ballon_idx.popleft())
        ballon_idx.rotate(-i+1)
    else: # i < 0
        paper.popleft()
        paper.rotate(-i) # -(-paper) -> 양수가 됨
        print(ballon_idx.popleft())
        ballon_idx.rotate(-i)