문제
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은 적혀있지 않다.
출력
첫째 줄에 터진 풍선의 번호를 차례로 나열한다.
| 예제 입력 | 예제 출력 |
|---|---|
| 5 3 2 1 -3 -1 | 1 4 5 3 2 |
풀이
설계
- 풍선들의 리스트를 받을 때 (index, number)의 형태로 받아 리스트 balloons에 입력한다.
- 풍선 리스트에서 1번째 요소를 꺼내어 인덱스를 answer에 추가하고 number의 수만큼 이동한다.
- 이동한 요소의 인덱스 값을 answer에 추가한다.
- 다음 이동할 인덱스 값을 계산한다. 이때 리스트를 순회한다는 점과 현재 인덱스가 다음 인덱스보다 크냐 작냐에 따라 계산을 달리한다.
- 상기 과정을 balloons가 빌 때까지 반복한다.
코드
from collections import deque
n = int(input())
balloons = deque(enumerate(map(int, input().split())))
answer = []
while balloons:
index, number = balloons.popleft()
answer.append(str(index+1))
if number > 0:
balloons.rotate(-(number-1))
elif number < 0:
balloons.rotate(-number)
print(" ".join(answer))최초 코드는 다음과 같았다.
n = int(input())
balloons = list(enumerate(map(int, input().split())))
current_index = 0
answer = []
while balloons:
balloons_length = len(balloons)
answer.append(str(balloons[current_index][0]+1))
current_number = balloons[current_index][1]
next_index = (current_index + current_number) % balloons_length
if next_index > current_index:
next_index -= 1
del balloons[current_index]
current_index = next_index
print(" ".join(answer))최초 코드에서는 현재 인덱스와 다음 인덱스의 크기를 비교하여 인덱스의 값을 조절하는 형태로 구현하려고 했으나, '5 // -5 -5 -5 -5 -5'의 반례를 통과하지 못하였다(답: 1 5 3 2 4).
결국 최종 코드에서는 deque의 rotate 메서드를 이용해 허무할 정도로 쉽게 해결. deque를 안 쓰더라도 for문을 돌려 각 방향별로 삭제와 삽입을 반복하면 해결할 수 있다.
시작할 때 큐를 사용해야겠다고 마음먹기만 했어도 금방 해결할 수 있는 문제였는데, 처음 떠올린 방식만 고집하다가 시간만 오지게 날려먹은 케이스. 자료 구조나 라이브러리 등을 잘 떠올려 시도해볼 수 있도록 연습할 필요가 있을 듯하다.
