Koala - 14기/코딩테스트 준비 스터디

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

beans3142 2024. 4. 12. 16:18

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

 

2346번: 풍선 터뜨리기

1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선

www.acmicpc.net

 

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

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

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

맨 처음 덱의 상태이다.

3 2 1 -3 -1

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

2 1 -3 -1

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

1 -3 -1 2

이렇게 된다.

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

-3 -1 2

-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)