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

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

아니 이거 푸는데 너무 오래 걸려서 옛날에 푼 거를 봤는데

리스트 크기가 바뀔 때, 인덱스를 출력해야 하는 문제를 맨날 못 풀었던 거 같아서 

정리를 하려고 가져왔습니다.

---

이건 발상도 오래걸렸고, 코드 구현도 마지막에 가서 헤매었어요..

발상부터 다 갈아엎고 나서 다시 풀었습니다.

코테에 이런 문제 나오면.. 어휴 정말 끔찍하네

당하기 전에 정리해야지

---

문제는 간단합니다. 

풍선 속에 숫자가 있고 터트린 풍선에 있는 숫자만큼 이동하는 상황입니다.

터뜨린 풍선은 제외하고 움직입니다.

---

제 발상은 딕셔너리로 위치를 처리하고

큐로 풍선 움직임을 구현하자였습니다.

import sys
from collections import deque

n = int(sys.stdin.readline())
balloons = deque(map(int, sys.stdin.readline().split()))
balloons_dict = {balloons[idx]: idx + 1 for idx in range(n)} 
answer = []
index = 0
for _ in range(n):
    move = balloons[0]
    answer.append(balloons_dict[move]) # 정답에 순서 삽입
    if move < 0: # 이동 음수일 때는 뒤로 
        for _ in range(abs(move)):
            temp = balloons.pop()
            balloons.appendleft(temp)
    else: # 양수일 때는 앞으로 돌림
        for _ in range(move):
            temp = balloons.popleft()
            balloons.append(temp)
    balloons.remove(move) # 이미 터뜨린 풍선 제거
print(*answer)

코드를 살펴보면, 처음에 풍선에 들어있는 움직임을 받고, 그 크기와 순서를 딕셔너리에 넣습니다.

그리고 풍선을 앞으로 뒤로 돌려서 움직인 자리가 맨 앞으로 오게 만들고, 이미 터트린 풍선을 remove 합니다.

---

그래서 이런 식으로 구현했는데요, 예제는 맞는데 18%에서 틀렸습니다가 나오더라고요.

고민을 해봤는데, 문제를 바로 찾았습니다.

여기서 문제는 딕셔너리입니다.

"이동의 양이 겹치지 않는다"라는 말을 했으면 딕셔너리가 맞았을 겁니다.

근데 만약에 1번 풍선에도 3이 있고, 5번 풍선에도 3이 있으면?

그러면 3은 무조건 5번 풍선만 터뜨리게 됩니다. 

결론 : 딕셔너리는 "유니크" 조건이 있을 때만 사용해야 한다.

---

그래서 코드 구현을 어떻게 해야 하냐?

입력받을 때부터 순서를 같이 받으면 됩니다.

import sys
from collections import deque

n = int(sys.stdin.readline())
balloons = deque(enumerate(map(int, sys.stdin.readline().split()), start=1))  # 풍선 위치와 숫자를 함께 저장

answer = []
while balloons:
    idx, move = balloons.popleft()  # 풍선의 위치와 숫자를 추출
    answer.append(idx)  # 결과 리스트에 위치를 추가
    
    if move > 0:  # 오른쪽 이동
        move -= 1  # 현재 위치는 이미 제거되었으므로 1만큼 감소
    balloons.rotate(-move)  # deque를 사용하여 풍선을 회전

print(*answer)

순서를 같이 받으면 순서가 바뀌는 것을 신경 쓰지 않아도 됩니다...

이걸 발상을 못한 게 조금 신기하긴 한데, 차라리 실버 3문제에서 틀린 게 다행이라고 생각이 듭니다.