[백준-Python] 풍선 터뜨리기 : 2346번

🥈 Silver3

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

 

 

 

 

✅ 정답풀이

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

n=int(input())
notes=list(map(int,input().strip().split()))

#deck 생성 (풍선 번호,note)
deck=deque((i+1,note) for i,note in enumerate(notes))

result=[]

#터트릴 풍선을 맨앞으로 보내고 터뜨리기
for _ in range(n):
    #초기값=1번 풍선
    ballon,dx=deck.popleft() #풍선번호,이동값
    result.append(ballon) #result=[1,4,5,3,2]
    

    # ➡️ 방향이라면, 이미 풍선을 터뜨렸기 때문에 dx-1만큼 이동해야한다
    if dx>0:
        dx-=1
        
    #dx만큼 풍선 이동
    deck.rotate(-dx)




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

 

rotate함수의 존재를 모르고 있었기 때문에, dx만큼 인덱스를 더하고, range 벗어날때도 신경써야했고, 

터뜨릴 풍선을 맨앞으로 옮겨서 해야겠다는 생각을 하지 못했다...😮

그래서 중간에서 꺼내야하다보니 그럼 queue가 아닌데..? 어질어질했다

붙잡고있다가 결국 GPT의 도움을 받았는데, rotate와 터뜨릴 풍선을 맨앞으로 옮기면, 간단해진다.

 

💡 queue는 맨앞에서 꺼내는 자료구조임을 유념하면서, 맨앞을 기준으로 판단하는 로직을 짜도록 하자.

이전 문제들도 다 그렇게 풀어야 지금처럼 수월했다 😣

 

풍선번호를 출력해야하기 때문에, 풍선번호와 이동해야할 수를 튜플로 묶어서 deck을 생성하고

주어진 조건에서 가장 터지는 풍선은 1번 풍선이므로, popleft()로 나온 풍선번호, 이동값을 초기값으로 정의한다.

 

풍선을 터뜨렸다면, 쪽지에 써있는 값만큼 이동을 해주어야하는데, 이때 rotate를 사용하면 굉장히 편리하다.

하지만, 반대방향으로 이동하므로 부호(+/-)를 변경해줘야한다. 

 

 

❗️부호를 변경하기 전에, ➡️ 방향으로 이동한다면 이미 풍선을 터뜨리고 deck에서 값을 제거해버렸기 때문에 이동값-1을 해주어야한다!

 

for문을 순회하면서 다음 풍선을 rotate를 통해 맨앞으로 옮겨놨기 때문에, popleft로 값을 꺼내고 result에 넣어주면된당✨