[백준] 2346번: 풍선 터뜨리기 / 파이썬

문제 링크

---

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

풀이 코드

---

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

n = int(input())
q = deque(enumerate(map(int, input().split()))) # 수와 인덱스 같이 저장
dap = []

while q:
    idx, num = q.popleft()    # 제일 앞 요소 뽑아서 저장
    dap.append(idx + 1) # 순서 저장

    if num > 0:     # 수가 양수면
        q.rotate(-(num - 1))    
    elif num < 0:   # 수가 음수면
        q.rotate(-num)

print(*dap) # 출력

코드 해석

---

수열이 원형으로 빙글빙글 돌기 때문에 원형 덱을 사용하여 풀이하였다.

 

enumerate를 사용하면 각 수를 인덱스와 함께 저장 할 수 있다.

ex) [3, 2, 1, -3, -1] -> [(0, 3), (1, 2), (2, 1), (3, -3), (4, -1)]

따라서 pop을 하면 두 변수에 각각 저장이 가능하다.

 

rotate는 덱를 들어온 값 만큼 돌리는것이다.

양수면 시계방향, 음수면 시계 반대 방향으로 돌린다.

 

꺼낸 값이 음수인 경우 덱을 오른쪽으로 회전시킨다(-num).

값이 양수인 경우 왼쪽으로 회전시켜야 하지만

이미 풍선이 pop되었기 때문에 -(num-1) 값 만큼 회전시킨다.

 

 

원형을 구현하는게 생각보다 복잡했다.

체감 난이도: ★★★☆☆