링크 : https://www.acmicpc.net/problem/2346
2346번: 풍선 터뜨리기
1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선
www.acmicpc.net
- 문제
- 소요시간: 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. 리스트 내에 이중배열로 인덱스 넘버를 추가하는 코드를 알게되었다
2. rotate()를 하는 경우 그 인자를 잘 고려해서 나누어야 할 때도 있다.
'알고리즘(백준) > 자료구조' 카테고리의 다른 글
| [알고리즘/자료구조] 2800번 : 괄호제거 - python (0) | 2023.03.11 |
|---|---|
| [알고리즘/자료구조] 1874번 : 스택 수열 - python (0) | 2023.03.10 |
| [알고리즘/자료구조] 1966 번 : 프린터 큐 - python (0) | 2023.03.07 |
| [알고리즘/1935] 번 : 후위 표기식2 - python (0) | 2023.03.06 |
| [알고리즘/자료구조] 10866번 : 덱 - python (0) | 2023.03.05 |