[백준] 2346: 풍선 터뜨리기 - 파이썬[python]

다인·2024년 10월 10일

백준

목록 보기

77/112

다른 사람들 코드를 보면 enumerate와 deque의 rotate를 활용했다. 하지만 나는 enumerate는 떠올리지 못했고.. rotate라는 함수도 알지 못했기에 요세푸스 문제처럼 풀었다. 그리고 enumerate와 rotote도 활용해 보았다.

1. 내 코드

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

N = int(input())
num = list(map(int, input().split()))
queue = deque([i+1 for i in range(N)])
result = []

result.append(queue.popleft())
while queue:
    if num[result[-1]-1] > 0:
        for _ in range(num[result[-1]-1] - 1):
            queue.append(queue.popleft())
        result.append(queue.popleft())
    else:
        for _ in range(-(num[result[-1]-1]) - 1):
            queue.appendleft(queue.pop())
        result.append(queue.pop())

print(*result)

나는 enumerate를 떠올리지 못해 num 리스트와 queue를 따로 만들었다.
요세푸스 문제랑 동일한데, 종이에 음수가 적힐 때의 코드를 추가해 주었다.
처음에는 result.append(queue.popleft())를 양수와 음수 동일하게 쓰기 위해서 음수일 때 동일하게 queue.append(queue.popleft())를 썼고, 반복하는 숫자를 다르게 했었다.
예제에 끼워맞춰서 그런지 계산을 잘못해서 그런지.. 계속 틀렸습니다가 나와서 이 방법을 버리고 양수가 왜 맨 앞의 요소를 스택 뒤에 넣었는지를 떠올리며 음수일 때의 코드를 따로 썼다.
양수일 때 시계방향으로 움직여서 popleft를 써서 맨 뒤에 넣어주었고, 음수일 때는 반시계방향이니까 pop을 해서 맨 앞에 넣어주면 된다. (그림을 그려가면서 이해하니까 왜 이렇게 쓰는지 이해도 되며 코드도 떠올리기 쉬웠다.)

1-1. enumerate 사용

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

N = int(input())
queue = deque(enumerate(map(int, input().split())))
result = []


balloon, paper = queue.popleft()
result.append(balloon+1)
while queue:
    if paper > 0:
        for _ in range(paper - 1):
            queue.append(queue.popleft())
        balloon, paper = queue.popleft()
    else:
        for _ in range(-paper - 1):
            queue.appendleft(queue.pop())
        balloon, paper = queue.pop()
    result.append(balloon+1)

print(*result)

enumerate는 인덱스와 원소로 이루어진 튜플을 만들어준다.
솔직히 내 코드는 -1을 막 하고 보기 지저분했는데 깔끔해졌다.

2. rotate까지 사용

rotate()

rotate(양수)는 원형 모향의 리스트가 시계 방향으로 회전한다. 즉, 가장 뒤에 있던 요소가 가장 앞으로 이동한다.
rotate(음수)는 원형 모향의 리스트가 반시계 방향으로 회전한다. 즉, 가장 앞에 있던 요소가 가장 뒤로 이동한다.

여기서 헷갈렸던 게, 원형 자체가 시계 방향으로 이동하는 것이다. 원소들 전체가 시계 방향으로 도는 것이다. 아래와 같이 말이다.
처음에는 시계방향으로 돈다고 해서 2 3 4 5 1 순으로 배치된다고 착각해버렷다..
그래서 종이에 양수가 적혀있으면 rotate(양수)를 써야된다고 생각했는데 잘못된 것이다!! 왜냐면 그림을 살펴보면 이건 popleft한 요소를 append하는 걸 1번이 아닌 4번 반복한 것이기 때문이다.
따라서 종이에 양수가 적혀있으면 rotate(음수)를 사용해야 한다. 그리고 음수가 적혀있어야 rotate(양수)를 사용해야 하는 것이다.

코드

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

N = int(input())
queue = deque(enumerate(map(int, input().split()), start=1))
result = []


while queue:
    balloon, paper = queue.popleft()
    result.append(balloon)

    if paper > 0:
        queue.rotate(-(paper-1))
    else:
        queue.rotate(-paper)

print(*result)