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

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

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번 풍선의 순서대로 터지게 된다.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000)이 주어진다. 다음 줄에는 차례로 각 풍선 안의 종이에 적혀 있는 수가 주어진다. 종이에 0은 적혀있지 않다.

출력

첫째 줄에 터진 풍선의 번호를 차례로 나열한다.

예제 입력 1 복사

5
3 2 1 -3 -1

예제 출력 1 복사

1 4 5 3 2

 

문제 이해

- 풍선이 있고, 1번부터 풍선을 터뜨리면 그 안에 있는 수 만큼 이동해서 다음 풍선을 터뜨리는 문제입니다.

- 문제 자체는 요세푸스 문제와 비슷하기 때문에, 요세푸스 문제를 먼저 풀어보시는 것을 추천합니다.

- 요세푸스 문제와 같이 큐를 사용해서 배열 속 요소를 이동시켜가며 인덱스 0번째에 대해서 처리합니다.

- 이때 어떤 풍선을 터뜨렸을 때의 숫자가 양수인지, 음수인지에 따라서 방법이 달라집니다.

양수일 경우 : v-1회만큼 첫번째 요소를 배열의 좌에서 우로 이동(popleft -> append)

음수일 경우 : 절댓값(v)만큼 마지막 요소를 배열의 우에서 좌로 이동(pop -> appendleft)

이렇게 하는 이유는 while문 초기에 popleft 하는 과정 또한 순서를 이동시키는 것에 포함되기 때문입니다.

 

- 파이썬의 enumerate메소드를 통해 값과 인덱스에 동시에 접근합니다. 해당 문제의 결과로 원본 배열에서 인덱스를 출력해야하기 때문에 while문에서 인덱스와 값을 함께 다룹니다.

- 최종적으로 인덱스값을 출력해주면 됩니다.

 

코드1( 큐의 여러 함수를 통한 이동)

#2346 풍선 터뜨리기
from collections import deque

n = int(input())
arr = list(map(int, input().split()))
q= deque()
for idx,v in enumerate(arr):
    q.append((v,idx+1))
result = []
while q:
    v,idx = q.popleft()
    if v > 0 and q:
        for i in range(v-1):
            k = q.popleft()
            q.append(k)
    elif v < 0 and q:
        for i in range(abs(v)):
            k = q.pop()
            q.appendleft(k)
    result.append(idx)

for i in result:
    print(i, end=' ')

 

 

또한, 파이썬에서 제공하는 덱의 rotate함수를 사용할 수도 있습니다.

rotate함수의 경우 rotate(2)를 할 경우 pop->appendleft 를 2번 하는 것과 같기 때문에(v가 음수일때와 같음)

양수, 음수의 경우를 반대로 생각해야 합니다.

 

코드2 (deque - rotate 함수)

#2346 풍선 터뜨리기
from collections import deque

n = int(input())
arr = list(map(int, input().split()))
q= deque()
for idx,v in enumerate(arr):
    q.append((v,idx+1))
result = []
while q:
    v,idx = q.popleft()
    if v > 0 and q:
        q.rotate(-(v-1))
    elif v < 0 and q:
        q.rotate(-v)
    result.append(idx)

for i in result:
    print(i, end=' ')