[백준] 2346번 : 풍선 터뜨리기 (스택/큐(덱) 실버Ⅲ) - Python

문제

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

접근

이전에 비슷한 문제를 풀어본 적이 있다.

https://chaeyami.tistory.com/180

[백준] 11866번 : 요세푸스 문제 0 (스택/큐 실버Ⅴ)

다만 이 때는 자리에 순서가 정해져있었고, 따라서 한 방향으로만 삭제해 단순 큐로만으로도 구현이 가능했다.

그러나 이번엔 삭제하는 방향이 양쪽이어서, 이전과 같은 방법으로는 불가

예제1에서, 입력이 3 2 1 -3 -1 이므로

풍선의 초기 상태는 이렇다.

그리고 첫번째 풍선을 터트리면 3칸 오른쪽으로 이동해야 하므로,

4번 풍선을 deque에 가장 앞 요소로 만들고 다시 돌려야 한다는 것을 알 수 있다. 

내가 오른쪽으로 이동해서 도착한 곳을 다시 시작점으로 돌리려면 반대로 풍선은 왼쪽으로 돌려야 한다는 것

그러면 아래 그림처럼 되고, 다시 진행하는 것이다.

풍선의 배치에서 n칸 오른쪽으로 이동해 해당 풍선을 가장 처음 요소로 만든다 = 풍선 전체를(deque를) 왼쪽으로 돌린다.

그래서 사용한 것이 deq.rotate이다.

이는 파이썬에서 지원하는 deque자료형의 메서드인데, 양방향 큐의 장점을 살려 원하는 방향으로 회전하게 해 준다.

deque.rotate(n): deque를 n만큼 회전한다(양수면 오른쪽, 음수면 왼쪽)

deq.rotate가 양수면 오른쪽으로 회전하고, 음수면 왼쪽으로 회전하므로

우리는 쪽지가 양수면 음수로 넣어주고, 쪽지가 음수면 양수로 넣어서 회전시켜줘야 한다.

또한 pop으로 요소를 뺀 후에 rotate시켜줘야 하는데,

이 말은 즉 rotate시켜주는 시점에는 이미 나머지 풍선들이 왼쪽으로 한칸씩 이동한 것이므로, rotate(-1)이 된 상태나 다름없다.
(위 그림의 두 번째 상태에서 이미 2번 풍선이 1번이 되어있다. = rotate(-1) 되어있다.)

따라서 쪽지가 양수일 때(음수로 rotate)는 쪽지에 주어진 수보다 한 칸 적게 회전시켜야 한다.

풀이과정

풍선 안에 적힌 수가 주어지므로, 각 수가 자리한 위치 = 풍선 번호를 먼저 정해준다.

enumerate를 사용해서 각 수를 인덱스와 함께 저장되도록 하고,

이를 다시 deque에 담아준다.

import sys
from collections import deque

input = sys.stdin.readline
n = int(input())

deq = deque(enumerate(map(int, input().split()))) 
'''
입출력 예 1번에서,
enumerate(map(int, input().split())) 
=> [(0, 3), (1, 2), (2, 1), (3, -3), (4, -1)]
'''

그리고 덱이 비어있지 않은 동안

• 덱의 가장 처음 요소를 꺼내 해당 값(쪽지)의 인덱스(풍선 번호)를 answer 리스트에 추가
• 꺼낸 값(쪽지)이 양수인 경우 덱을 왼쪽으로 (값-1)만큼 회전
• 음수인 경우 덱을 오른쪽으로 값만큼 회전
• 반복

while deq:
    idx, now_turn = deq.popleft()
    answer.append(idx + 1)

    if now_turn > 0:
        deq.rotate(-(now_turn - 1))
    elif now_turn < 0:
        deq.rotate(-now_turn)

• 덱이 비면 결과 출력

전체 풀이 코드

import sys
from collections import deque

input = sys.stdin.readline
n = int(input())

deq = deque(enumerate(map(int, input().split())))
answer = []

while deq:
    idx, now_turn = deq.popleft()
    answer.append(idx + 1)

    if now_turn > 0:
        deq.rotate(-(now_turn - 1))
    elif now_turn < 0:
        deq.rotate(-now_turn)

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