[알고리즘/자료구조] 2346 번 : 풍선 터뜨리기 - python

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

2346번: 풍선 터뜨리기

 

---

• 문제
• 소요시간: 45분 20초

---

• 설계하기(접근방법) 

1. n을 입력받는다

2. 종이 리스트를 입력받는다.

[3,2,1,-3,-1]

+ 각각의 원소에 순서 넘버를 추가한다

[[3,1],[2,2],[1,3],[-3,4],[-1,5]]

 

for i in range(5) 동안:

 

index[0]인 리스트를 popleft()하고 popnum에 저장한다 

-> [[2,2],[1,3],[-3,4],[-1,5]]

 

popnum = [3,1]

이 중에서 첫번째 원소는 이동해야하는 칸수 = rotatenum 이고

두번째 원소는 출력해야할 풍선의 넘버이다

 

rotatnum >= 0 인경우 :

원래  3칸을 이동해야하나, popleft()로 원소가 1개 제거되었으므로 rotatenum -1 만큼 뒤로 이동시킨다

[3,1,2,4,5]에서

오른쪽 3칸은 4이지만

[1,2,3,5]에서

오른쪽 3칸은 5가 되어버리기 때문이다.

그러기 때문에 1칸 덜 가야 한다.

즉 -> balloon.rotate(-(rotatenum-1))

 

rotatnum < 0인경우:

popleft()를 하기 전이나 후나 (-)음수 만큼 이동하는 것에는 영향을 끼치지 않는다

 

이 방법을 반복하여 deque가 빌 때까지 popleft()를 진행하고 인덱스를 출력한다

 

 

 

---

• 코드(출력)

from collections import deque

n = int(input())

balloon = list(map(int, input().split()))

for i in range(n):
    balloon[i] = [balloon[i]]
    balloon[i].append(i+1)

balloon = deque(balloon)

for i in range(n):
    popnum = balloon.popleft()
    rotatenum = popnum[0]
    print(popnum[1], end=' ')
    if rotatenum >= 0:
        balloon.rotate(-(rotatenum - 1))
    else:
        balloon.rotate(-(rotatenum))

---

• 얻어갈 부분

1. 리스트 내에 이중배열로 인덱스 넘버를 추가하는 코드를 알게되었다

n = int(input())

balloon = list(map(int, input().split()))

for i in range(n):

    balloon[i] = [balloon[i]]

    balloon[i].append(i+1)

2. rotate()를 하는 경우 그 인자를 잘 고려해서 나누어야 할 때도 있다.