백준: 2346 풍선 터뜨리기

문제

2346번: 풍선 터뜨리기

 

문제 풀이

 각 풍선에 다음 순번 풍선으로 가기 위한 값들이 적혀있다. 해당 값을 기준으로 음수이면 좌측, 양수이면 우측으로 다음에 터트릴 풍선을 선택한다. 터트린 순서대로 풍선의 번호(Index)를 기록한 후, 정답으로 반환하는 문제이다. 문제를 풀기 위해 아래와 같이 접근하였다.

 

• 모듈러 연산을 통해, 터트리고자 하는 풍선을 바로 찾을 수 있을 것이다.
• 하지만, 입력된 풍선들 전체를 left, right shift 하는 방식을 통해 답을 찾고자 했다.
  • Python의 경우, list는 shift를 지원하지 않는다.
    • 이는 `pop(0)`와 `insert(index, value)`와 같은 메소드들이 O(N)의 시간을 소비하기 때문이다.
  • 따라서 shift가 필요한 경우, `deque`를 활용하여 문제를 풀어야 한다.

 

코드

from sys import stdin
from collections import deque

if __name__ == "__main__":
    N = int(stdin.readline())
    q = deque(enumerate(map(int, stdin.readline().split())))
    answer = []

    while True:
        idx, paper = q.popleft()
        answer.append(idx + 1)

        if not q:
            break

        if paper > 0:
            # rotate(-) == append(q.popleft())
            q.rotate(-(paper - 1))
        elif paper < 0:
            # rotate(+) == appendleft(q.pop())
            q.rotate(-paper)

    print(' '.join(map(str, answer)))