[Python] 백준/BOJ 2346번: 풍선 터뜨리기

문제 링크

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

---

문제

1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선이 있다. 각 풍선 안에는 종이가 하나 들어있고, 종이에는 -N보다 크거나 같고, N보다 작거나 같은 정수가 하나 적혀있다. 이 풍선들을 다음과 같은 규칙으로 터뜨린다.

우선, 제일 처음에는 1번 풍선을 터뜨린다. 다음에는 풍선 안에 있는 종이를 꺼내어 그 종이에 적혀있는 값만큼 이동하여 다음 풍선을 터뜨린다. 양수가 적혀 있을 경우에는 오른쪽으로, 음수가 적혀 있을 때는 왼쪽으로 이동한다. 이동할 때에는 이미 터진 풍선은 빼고 이동한다.

예를 들어 다섯 개의 풍선 안에 차례로 3, 2, 1, -3, -1이 적혀 있었다고 하자. 이 경우 3이 적혀 있는 1번 풍선, -3이 적혀 있는 4번 풍선, -1이 적혀 있는 5번 풍선, 1이 적혀 있는 3번 풍선, 2가 적혀 있는 2번 풍선의 순서대로 터지게 된다.

---

풀이

1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선이 있으므로 원형큐이다. 파이썬에서 원형큐를 쓰기 위해 deque을 사용했다.

 

(1) 풍선 안의 종이에 적혀 있는 수를 balloon이라는 deque으로 입력받는다.

enumerate()를 이용하여 각 풍선 안의 종이에 적혀 있는 수와 풍선 번호(index)를 함께 형성한다. 예를 들어, 3 2 1 -3 -1을 입력하였을 때, 원래는 deque([3, 2, 1, -3, -1])로 저장되지만, enumerate()를 이용하면 deque([(0, 3), (1, 2), (2, 1), (3, -3), (4, -1)])로 저장된다.

 

(2) 풍선 안의 종이에 적혀 있는 수(tmp)가 양수이면 오른쪽으로 이동한다.

deque 상에서는 왼쪽으로 이동하는 것이므로 rotate() 괄호 안에 음수를 적어야 한다.

tmp가 양수이므로 음수가 되도록 -를 붙여준다.

주의할 점: 1번 풍선을 popleft() 했기 때문에 왼쪽으로 한 번 이동했다고 볼 수 있어 tmp에서 1을 빼줘야 한다.

 

(3) 풍선 안의 종이에 적혀 있는 수(tmp)가 음수이면 왼쪽으로 이동한다.

마찬가지로 deque 상에서는 오른쪽으로 이동하는 것이므로 rotate() 괄호 안에 양수를 적어야 한다.

tmp가 음수이므로 양수가 되도록 -를 붙여준다.

---

정답 코드

from collections import deque

n = int(input())
balloon = deque(enumerate(map(int, input().split())))

for i in range(n):
    idx, tmp = balloon.popleft()
    print(idx + 1, end=' ')
    if tmp > 0:
        balloon.rotate(-(tmp - 1))
    else:
        balloon.rotate(-tmp)

---

막힌 부분 (틀린 코드)

from collections import deque

n = int(input())
balloon = deque(map(int, input().split()))
ord = list(balloon)

while balloon:
    tmp = balloon.popleft()
    if tmp > 0:
        balloon.rotate(-(tmp - 1))
    else:
        balloon.rotate(-tmp)
    print(ord.index(tmp) + 1, end=' ')

처음에 enumerate 알지 못하고 풍선의 deque와 같은 list를 생성해서 터진 풍선의 index를 출력하도록 하였다.

반례는 같은 넘버를 가진 풍선이 있을 경우이다.

이 게시글을 통해 enumerate를 알게 되어 enumerate를 이용하여 풀었다.