[Python] 백준 2346번 (풍선 터뜨리기) [실버3]

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

풍선이 원형으로 놓여 있으니까 숫자를 양쪽에서 빼거나 넣을 수 있어야 하므로 deque를 써야한다.

 

처음에 이 문제를 deque의 append와 pop으로만 풀려고 했는데 코드가 너무 복잡해졌다..

 

deque에 대해서 조금 더 알아보니까 rotate()라는 메서드가 존재한다는 것을 깨달았다.

 

rotate(3)이라면 deque의 오른쪽에서 값을 뺀 뒤 왼쪽으로 넣는걸 3번 반복한다.

 

반대로 rotate(-3)이라면 deque의 왼쪽에서 값을 뺀 뒤 오른쪽으로 넣는걸 3번 반복한다.

 

rotate()메서드를 알고 나니 코드가 엄청 간결해졌다.

 

정답

import sys
from collections import deque

N = int(sys.stdin.readline())

dq = deque()
baloons = list(map(int, sys.stdin.readline().split()))

for index, move in enumerate(baloons):
    dq.append((index+1, move))

index, move = dq.popleft()
sys.stdout.write(str(index) + " ")
while dq:
    if move > 0:
        dq.rotate(-(move-1))
    else:
        dq.rotate(-move)
    
    index, move = dq.popleft()
    sys.stdout.write(str(index) + " ")

 

풀이

1. 풍선을 담을 dq와 현재 풍선 리스트 baloons를 초기화한다.

dq = deque()
baloons = list(map(int, sys.stdin.readline().split()))

 

2. 풍선 번호인 index+1와 움직이는 횟수 move를 튜플로 담아준다. (시작 인덱스가 1이므로 index+1)

for index, move in enumerate(baloons):
    dq.append((index+1, move))

 

3. 첫 번째 풍선은 무조건 터트리고 인덱스를 출력한다.

index, move = dq.popleft()
sys.stdout.write(str(index) + " ")

 

4. dq에 튜플이 존재하는 동안에는 while문을 계속 반복한다.

 

이후에 move값이 양수냐 음수냐에 따라서 회전시키는 숫자가 다른다. 예시를 통해서 이해해보자.

 

일단 우리는 풍선을 무조건 왼쪽에서 꺼내서 터트린다고 가정한다.

 

만약 move = 3이라면 왼쪽에서 2개의 풍선을 오른쪽으로 옮겨준 뒤 3번째 풍선은 꺼내서 터트리면 된다. 따라서 3번을 회전시킬 필요가 없고 3-1번만 회전시키면 된다. 따라서 move가 양수일 땐 rotate(-(move-1))가 된다.

 

만약 move = -3이라면 오른쪽에서 3개의 풍선을 왼쪽으로 옮겨준 뒤 왼쪽에서 첫 번째 풍선을 꺼내서 터트린다. 우리는 풍선을 무조건 왼쪽에서 터트린다는 점을 잊지 말자. 따라서 move가 음수일 땐 rotate(-move)가 된다.

while dq:
    if move > 0:
        dq.rotate(-(move-1))
    else:
        dq.rotate(-(move))
    
    index, move = dq.popleft()
    sys.stdout.write(str(index) + " ")