[Python] 백준 2346 풍선 터뜨리기

 

문제 분석

• 1~N까지 풍선이 원형으로 놓여있다.
• i번 풍선의 오른쪽은 i+1, 왼쪽에는 i-1 풍선
• 1번 풍선의 왼쪽에 N번 풍선, N번 풍선 오른쪽에 1번 풍선
• 각 풍선에는 종이가 한 장씩 들어있고, -N ≤ 종이에 적힌 수 ≤ N

• 풍선을 터뜨리는 규칙
• 제일 먼저 1번 풍선
• 그 다음은 풍선안의 종이를 꺼내서 종이에 적힌 값 만큼 이동하여 다음 풍선을 터뜨림
• 양수 : 오른쪽 이동, 음수 : 왼쪽 이동
• 이미 터진 풍선은 빼고 이동
• 풍선이 터진 순서대로 출력

 

코드 설계

• 종이에 적힌 숫자가 양수일 때 / 음수일 때 모두 고려

 

정답 코드

import sys
input = sys.stdin.readline

from _collections import deque

n = int(input())
d_paper = deque(list(map(int, input().split())))
d_idx = deque([i for i in range(1, n+1)])
ans = []

while d_paper :
    paper = d_paper.popleft()
    ans.append(d_idx.popleft())

    if len(d_paper) == 0 :
        break

    if paper > 0 :
        for _ in range(paper-1) :
            tmp_p = d_paper.popleft()
            tmp_i = d_idx.popleft()
            d_paper.append(tmp_p)
            d_idx.append(tmp_i)
    else :
        for _ in range(abs(paper)) :
            tmp_p = d_paper.pop()
            tmp_i = d_idx.pop()
            d_paper.appendleft(tmp_p)
            d_idx.appendleft(tmp_i)

print(' '.join(map(str, ans)))

 

다른 사람 코드 1

https://velog.io/@hygge/Python-%EB%B0%B1%EC%A4%80-2346-%ED%92%8D%EC%84%A0-%ED%84%B0%EB%9C%A8%EB%A6%AC%EA%B8%B0-deque

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

n = int(input())
q = deque(enumerate(map(int, input().split())))
ans = []

while q:
    idx, paper = q.popleft()
    ans.append(idx + 1)

    if paper > 0:
        q.rotate(-(paper - 1)) # 양수의 경우 이미 앞의 숫자가 빠져 -1
    elif paper < 0:
        q.rotate(-paper)

print(' '.join(map(str, ans)))

• enumerate 를 사용해서 덱에 인덱스와 종이 값을 튜플로 묶어 하나의 원소로 저장

• enumerate 사용 전
  deque([3, 2, 1, -3, -1])
• enumerate 사용 후
  deque([(0, 3), (1, 2), (2, 1), (3, -3), (4, -1)])

deque.rotate()

rotate(-1)은 원형 큐를 반시계방향으로 1칸 회전시키고, rotate(1)은 시계방향으로 1칸 회전시킨다고 생각하면 쉽다.