[백준/Python] 2346 풍선 터뜨리기

https://www.acmicpc.net/problem/2346

2346번: 풍선 터뜨리기

 

요세푸스 문제 비슷한 유형이다. 원형 큐 혹은 덱을 사용해서 풀 수 있는데 나는 덱을 이용하여 풀었다.

일단 문제를 해결하기 위해서 값을 빼낼 위치 한 곳을 정해주어야 한다. 

왼쪽으로 이동, 오른쪽으로 돌리는 연산은 각각 append(popleft())와 appendleft(pop())로 구현을 할 수 있다.

맨 처음 덱의 상태이다.

3

2

1

-3

-1

popleft해준 뒤 나온 값이 양수이므로 오른쪽 3칸 앞의 값을 빼야한다 그런데 그 사이의 있는 값을 그냥 건너뛰어도 되지만 그 값들을 큐의 반대편으로 보내주어도 된다.

2

1

-3

-1

여기서 맨 앞의 값을 popleft해준 뒤 append시켜주면

1

-3

-1

2

이렇게 된다.

반대로 -인 경우는 다음과 같을 것이다

-3

-1

2

1

-3을 빼주고

-1

2

1

여기서 맨 뒤의 값을 pop해서 appendleft 해준다.

1

-1

2

이런 식으로 값이 모두 사라질 때 까지 반복해주면 된다.

 

from sys import stdin
from collections import deque
input=stdin.readline

n=int(input())
bol=deque()
for idx,val in enumerate(map(int,input().split())):
    bol.append([val,idx+1])
front=bol.popleft()
ans=[front[1]]
while bol:
    if front[0]>0:
        for i in range(front[0]):
            bol.append(bol.popleft())
        front=bol.pop()
    else:
        for i in range(abs(front[0])):
            bol.appendleft(bol.pop())
        front=bol.popleft()
    ans.append(front[1])
print(*ans)