[백준/baekjoon] 2346번 풍선 터뜨리기 (파이썬)

내 제출

from collections import deque


# 풍선 터뜨리는 함수(풍선 개수, 풍선에 적힌 번호 리스트)
def pop_balloons(balloon_cnt, balloon_list):
    balloons = deque([(i + 1, balloon_list[i]) for i in range(balloon_cnt)])
    after_pop = []

    while balloons:
        index, move = balloons.popleft()
        after_pop.append(index)

        if not balloons:
            break

        if move > 0:
            balloons.rotate(-move + 1)
        else:
            balloons.rotate(-move)

    return after_pop


# 입력
n = int(input())
# 풍선 안에 적힌 수
numbers = list(map(int, input().split()))

# 결과 출력
result = pop_balloons(n, numbers)
# print(" ".join(map(str, result)))
print(*result)

 

문제 접근

- 주어진 풍선의 수 n과 풍선 안에 적힌 수 'numbers'를 입력으로 받음.

- 덱을 사용하여 풍선을 하나씩 터뜨리면서 해당 숫자만큼 이동하는 과정을 반복.

- 이동은 'rotate'함수를 사용해서 회전시키는 방식으로 오른쪽 또는 왼쪽으로 가게 함.

 

코드 설명(간단히,,)

balloons = deque([(i + 1, balloon_list[i]) for i in range(balloon_cnt)])

- 리스트 컴프리헨션(https://taetaegom.tistory.com/25)과 deque를 사용

- 1번부터 N번까지 번호가 매겨진 풍선들과 각 풍선 안에 적힌 숫자를 덱에 순서대로 저장 (자세한 설명↓)

• for i in range(balloon_cnt): 이 반복문은 0부터 n-1까지 반복. 여기서 balloon_cnt 은 풍선의 총 개수.
• i + 1: 풍선의 번호. 저장은 0번 index부터 되지만 풍선의 실제 번호는 1부터 시작하므로 i + 1을 사용.
• balloon_list[i]: i 번째 풍선 안에 적힌 숫자낸다. balloon_list라는 리스트는 사용자로부터 입력받은 각 풍선 안의 숫자들을 담고 있다.
• (i + 1, numbers[i]): 각 풍선의 번호와 그 안의 숫자를 튜플로 묶은 것으로 각 풍선은 튜플 형태로 구성된다(풍선 위치 번호, 풍선 종이에 적힌 숫자)
• deque([...]): 여기서 리스트 컴프리헨션을 사용하여 생성된 튜플들의 리스트를 deque로 변환.

    while balloons:
        index, move = balloons.popleft()
        after_pop.append(index)

        if not balloons:
            break

        if move > 0:
            balloons.rotate(-move + 1)
        else:
            balloons.rotate(-move)

- 덱(deque)에 있는 모든 풍선을 터뜨릴 때까지 반복.

- 모든 풍선을 차례대로 터뜨리고, 그 순서를 리스트에 기록함 => 최종적으로 풍선이 터진 순서를 나타냄.

1. index, move = balloons.popleft()
   1. 이 코드는 덱의 왼쪽(앞쪽)에서 풍선을 하나 제거한다.
   2. 이 풍선은 현재 터뜨릴 풍선이다.
   3. popleft() 함수는 풍선의 번호(index)와 그 안의 종이에 적힌 숫자(move)를 반환함.
2. after_pop.append(index)
   1. 현재 터뜨린 풍선의 번호를 after_pop 리스트에 추가.
   2. 이 리스트는 터진 풍선의 순서를 기록.
3. if not balloons: break
   1. 만약 모든 풍선이 터졌다면 (balloons 덱이 비어 있다면), 루프를 종료.
4. if move > 0
   1. 여기서 move 값이 양수인 경우와 음수인 경우를 나누어 처리.
   2. move 값은 다음에 터뜨릴 풍선으로 이동하는 데 필요한 거리.

• 양수인 경우 (move > 0): 오른쪽으로 이동해야 함. balloons.rotate(-move + 1) 코드는 덱을 왼쪽으로 회전시켜, 사실상 오른쪽으로 이동하는 효과를 낸다. move 값만큼 이동한 다음, 현재 터뜨린 풍선을 제외하기 위해 1을 더 빼준다. 예를 들어, move가 3이라면, 실제로는 2번째 오른쪽 풍선을 터뜨려야 하므로 덱을 왼쪽으로 2번 회전시킨다.
• 음수인 경우: 왼쪽으로 이동해야 한다. balloons.rotate(-move) 코드는 덱을 오른쪽으로 회전시킨다. 음수 값인 move가 이미 왼쪽 이동 거리를 나타내므로, 덱을 오른쪽으로 move의 절대값만큼 회전시키면 된다. 예를 들어, move가 -2라면, 실제로는 2번째 왼쪽 풍선을 터뜨려야 하므로 덱을 오른쪽으로 2번 회전시킨다.

결과

 

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

2346번: 풍선 터뜨리기