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

1. 문제 

안에 숫자가 적힌 풍선 N 개가 원형으로 놓여져 있을 때 
1번을 터뜨려 안에 적힌 숫자만큼 이동해 풍선을 터뜨리는 문제 
숫자가 양수이면 오른쪽, 음수이면 왼쪽으로 이동한다  

2. 제한

시간 제한 2초 
메모리 제한 4MB 

 

3. 알고리즘 분류 

* 자료 구조

* 덱

 

4. 접근 방식 

풍선들이 원형 구조를 이루고 있기 때문에 Deque 을 사용한다 

🐣 정글에서도 많은 칭구들이 처음에 혼란을 겪었지만 Deque 는 디큐가 아니고 덱이라고 읽는다 🐣

Deque 는 양쪽 끝에서 삽입과 삭제가 모두 O(1) 이기 때문에 원형 리스트를 다루는 데 효과적이다 

풍선을 왼쪽 또는 오른쪽으로 이동해야 하므로, Deque 앞/ 뒤에서 쉽게 풍선을 넣고 뺄 수 있다 

풍선을 터뜨린 후에 해당 풍선을 삭제해야 하는데, 이 때 Deque 를 사용하여 

풍선의 순서를 관리하고 터뜨릴 풍선을 선택하면 효율적으로 진행할 수 있다 

 

풍선 안에 적힌 숫자 move 가 양수일 경우, 오른쪽으로 이동해야 한다 

자기 자신을 제외하고 나머지를 이동해야 하므로 move 에 -1 을 해줘서 move-1 만큼 이동한다 

rotate 는 기본적으로 음수 값을 쓰면 왼쪽으로 이동하고, 양수 값을 쓰면 오른쪽으로 이동하는데 

오른쪽으로 move 만큼 이동한 것과 왼쪽으로 move-1 만큼 이동한 것은 같은 결과를 가진다
🐣 오른쪽으로 이동하게 되면 리스트의 길이를 고려해야 해서 왼쪽으로 이동하는 게 직관적이다  

그래서 move-1 을 음수로 바꾸어 (-(move-1)) 을 사용하면 해당 숫자를 맨 앞으로 이동시킬 수 있다 

5. 전체 코드 w/ Python 

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

# 1번부터 N번까지 N개의 풍선이 원형으로 놓여져 있다 
# 1번 풍선을 터뜨리고 안에 있는 종이를 꺼내어 
# 그 종이에 적혀있는 값만큼 이동하여 다음 풍선을 터뜨린다 
# 양수가 적혀 있을 때는 오른쪽, 음수는 왼쪽으로 이동한다 
# 이동할 때 이미 터진 풍선은 빼고 이동한다 
# 각 풍선 안의 종이에 적혀 있는 수가 주어질 때 
# 터진 풍선의 번호를 차례로 나열한다 

from collections import deque
import sys 

n = int(input()) # 풍선의 개수
# 풍선 안에 적힌 숫자 입력 받으면서 (풍선 번호, 적힌 숫자) 튜플 형태로 저장 
balloon = deque(enumerate(map(int, input().split()), start=1))
result = [] # 결과를 저장할 리스트  

# 첫번째 풍선 터뜨리기, num 은 풍선 번호 move 은 적힌 (이동할) 숫자
num, move = balloon.popleft() 
result.append(num)

while balloon:
    # 양수이면 오른쪽으로 이동, -1은 자기 자신 제외
    if move > 0:
        balloon.rotate(-(move-1))
    # 음수면 왼쪽으로 이동 
    else:
        balloon.rotate(-move)
    
    # 다음 풍선 터뜨리기 
    num, move = balloon.popleft()
    result.append(num)

# 리스트의 원소를 공백 기준으로 펼쳐서 출력하기 
print(*result)