📜 문제 이해하기
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번 풍선이 나온다.
- 가장 먼저 1번 풍선을 터뜨리고 값을 확인한다.
- 풍선안의 값만큼 이동한다. 이 때 양수라면 오름차순으로 진행되고 음수라면 내림차순으로 진행된다.
- 도착한 풍선을 터트리고 값을 확인한다.
- 3 ~ 4의 과정을 반복해 모든 풍선을 터트린 후 터트린 순서를 출력한다.
✏️ 계획 수립
가장 먼저 떠오른 방법은 환형 큐이다.
환형 큐로 풍선의 인덱스와 값을 넣을 순서대로 넣은뒤 1번부터 터트리고 해당 값만큼 오른쪽 또는 왼쪽으로 이동하면 된다.
이때 오른쪽과 왼쪽의 차이는 오름차순 내림차순이라 정의한다.
아래는 자세한 방법이다.
- 풍선큐에 [인덱스, 풍선내용]을 순서대로 enqueue한다.
- 큐의 가장 앞쪽을 터트리고 터트린 순서에 인덱스 값을 기록한다.
- 만약 풍선 내용이 이전 풍선 내용과 다르다면 큐를 뒤집는다. (오름차순과 내림차순을 변경하기 위해.. 처음은 오름차순)
- 풍선 내용의 절댓값만큼 회전한다.
- 2 ~ 4 과정을 풍선의 갯수만큼 반복한다.
💻 계획 수행
from collections import deque
if __name__ == '__main__':
balloon_num = int(input())
balloon_queue = deque([i + 1, gap] for i, gap in enumerate(map(int, input().split())))
pop_order = []
last_value = 1
for _ in range(balloon_num):
value_in_balloon = balloon_queue.popleft()
pop_order.append(value_in_balloon[0])
if last_value * value_in_balloon[1] < 0:
balloon_queue.reverse()
balloon_queue.rotate(1 - abs(value_in_balloon[1])) # -(abs(value_in_balloon[1]) - 1)
last_value = value_in_balloon[1]
print(*pop_order, sep=' ')🤔 회고
이번 문제 역시 환형 큐를 사용하는 문제였다.
이 문제를 풀면서 가장 고민했던 부분은 양수와 음수 처리 부분이었다.
처음에는 양수인지 음수인지 if문으로 확인해서 따로 코드를 분리했는데 코드가 너무 길어지고 직관적으로 보이지 않았다.
이 때 생각한것이 굳이 음수라고 뒤로갈 필요가 없고 음수를 양수같이 처리하면 되는거였다.
이에 따라 이전 값과 부호가 다를때마다 큐를 뒤집으면 결국 절댓값만큼 이동하면 문제가 해결되었다.
가장 최악의 케이스는 O(n-1)만큼 큐를 뒤집을 수도 있다.
이보다 더 좋은 알고리즘을 찾기위해 노력해야겠다.
