문제

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은 적혀있지 않다.

출력

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

풀이

deque을 사용하지 않은 코드

import sys

n = int(sys.stdin.readline())
balloon = list(map(int, sys.stdin.readline().split()))
for i in range(n):
    balloon[i] = (str(i+1), balloon[i])

answer = []  # 터진 풍선의 순서를 담는 리스트

move = balloon[0][1]  # 이동할 칸수
index = 0  # 풍선 인덱스
answer.append(int(balloon[0][0]))  # 터지는 풍선번호 추가
del balloon[0]  # 터진풍선 리스트에서 삭제
for i in range(n-1):
    if move > 0:
        index = (index + move -1) % len(balloon)
    else:
        index = (index + move) % len(balloon)
    move = balloon[index][1]
    answer.append(int(balloon[index][0]))
    del balloon[index]
print(*answer)

문제를 읽고 문제가 하라는대로 충실히 수행한 코드이다. 돌아가는데 문제는 없지만 리스트의 index가 리스트를 벗어났을 때의 경우와 모듈로 연산(Modulo Operation)을 처리하는게 생각보다 까다로운 문제였다.

이동방향에 따라 코드가 달라지는 것은 맨 앞의 풍선을 터뜨리면서 뒤에있는 풍선이 한칸 앞으로 오게되는데, 다음에 터뜨릴 풍선이 오른쪽에 있는 경우 오른쪽으로는 한칸 덜가도 된다는 의미이다.

deque의 rotate를 사용한 코드

import sys
from collections import deque

n = int(sys.stdin.readline())
balloon = deque(enumerate(map(int, sys.stdin.readline().split())))

while balloon:
    idx, num = balloon.popleft()
    print(idx+1, end = ' ')

    if num > 0:
        balloon.rotate(-(num-1))
    else:
        balloon.rotate(-num)

지금까지는 deque을 사용하면서 stack과 queue의 push, pop 등 비교적 간단한 연산만 처리했지만, 공부를 하면서 rotate기능을 처음 알게되었다. 이문제에 rotate를 이용하면 풍선을 터뜨리면서 요리조리 이동하는 과정을 간단하게 구현할 수 있게된다. 또한 앞의 풍선을 터뜨리는것도 popleft()를 사용하면 되기에 훨씬 간단하게 이 문제를 풀 수 있다.

단, 이문제에서 popleft를 사용하여 맨앞의 풍선을 터뜨리므로, 문제에서 이동하여 터뜨릴 풍선을 deque의 맨앞으로 가져와야한다. 즉 오른쪽의 풍선을 터뜨리려면 왼쪽방향으로 rotate해야하고, 왼쪽의 풍선을 터뜨리려면 오른쪽방향으로 rotate시켜야 문제의 조건을 충족시킬 수 있다.

위 사진은 오른쪽의 풍선을 터뜨리는 경우를 그림으로 표현한 것이다. 맨앞의 풍선이 터지면서 두번째 자리에 있던 풍선이 자연스럽게 맨앞으로 오게되면서 한 칸 덜가도 됨을 의미한다.

참고) deque.rotate

from collections import deque

test = deque([x for x in range(8)])
print(test)  # deque([0, 1, 2, 3, 4, 5, 6, 7])

# 오른쪽으로 회전
test.rotate(3)
print(test)  # deque([5, 6, 7, 0, 1, 2, 3, 4])

# 왼쪽으로 회전
test.rotate(-2)
print(test)  # deque([7, 0, 1, 2, 3, 4, 5, 6])