URL : https://www.acmicpc.net/problem/2346
문제
- 1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선이 있다. 각 풍선 안에는 종이가 하나 들어있고, 종이에는 -N보다 크거나 같고, N보다 작거나 같은 정수가 하나 적혀있다. 이 풍선들을 다음과 같은 규칙으로 터뜨린다.
- 우선, 제일 처음에는 1번 풍선을 터뜨린다. 다음에는 풍선 안에 있는 종이를 꺼내어 그 종이에 적혀있는 값만큼 이동하여 다음 풍선을 터뜨린다. 양수가 적혀 있을 경우에는 오른쪽으로, 음수가 적혀 있을 때는 왼쪽으로 이동한다. 이동할 때에는 이미 터진 풍선은 빼고 이동한다.
- 예를 들어 다섯 개의 풍선 안에 차례로 3, 2, 1, -3, -1이 적혀 있었다고 하자. 이 경우 3이 적혀 있는 1번 풍선, -3이 적혀 있는 4번 풍선, -1이 적혀 있는 5번 풍선, 1이 적혀 있는 3번 풍선, 2가 적혀 있는 2번 풍선의 순서대로 터지게 된다.
입력
- 첫째 줄에 자연수 N(1 ≤ N ≤ 1,000)이 주어진다. 다음 줄에는 차례로 각 풍선 안의 종이에 적혀 있는 수가 주어진다. 종이에 0은 적혀있지 않다.
출력
- 첫째 줄에 터진 풍선의 번호를 차례로 나열한다.
문제 풀이
- collections의 deque를 사용하여 풀었음
- nums : 풍선안에 들어간 숫자
- balloons : 풍선
- 로직 : 첫번째 풍선을 터뜨리고, 그 풍선안에 있는 숫자만큼 deque의 맨 앞으로 이동시킴
- 맨 앞으로 이동하는 방법은 deque의 rotate를 사용함
- 여기서 nums와 balloons를 같이 rotate해주어야 함
- deque의 rotate는 회전을 시키는건데, 양수로 들어오면 맨뒤에것이 앞으로 순서대로 옴, 음수가 들어오면 맨앞에것이 맨뒤로감
- 따라서 지금 nums의 음수와 반대로 움직이면 되서 양수이면 -로 바꾸고 음수이면 +로 바꿔줌
- num이 양수일경우엔 마지막에 +1을 해주어야 함. 아마도 0부터 시작해서 그런듯??
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from collections import deque
N = int(input())
nums = deque(list(map(int, input().split())))
balloons = deque(list(range(1, N+1)))
results = []
for i in range(N):
balloon = balloons.popleft()
results.append(balloon)
num = nums.popleft()
# num이 양수일경우 음수로 바꿔줌
if num > 0:
balloons.rotate(-num+1)
nums.rotate(-num+1)
# num이 음수일 경우 양수로 바꿔줌
else:
balloons.rotate(-num)
nums.rotate(-num)
for r in results:
print(r, end= ' ')
1
2
3
4
5
5
3 2 1 -3 -1
1 4 5 3 2
1
2
3
4
5
6
7
8
9
10
# Contain 1, 2, 3, 4, 5 in deq
deq = deque([1, 2, 3, 4, 5])
deq.rotate(1)
print(deq)
# deque([5, 1, 2, 3, 4])
deq.rotate(-1)
print(deq)
# deque([1, 2, 3, 4, 5])
1
2
deque([5, 1, 2, 3, 4])
deque([1, 2, 3, 4, 5])
1
1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from collections import deque
N = 5
nums = deque([3, 2, 1,- 3, -1])
balloons = deque(list(range(1, N+1)))
results = []
for i in range(N):
balloon = balloons.popleft()
results.append(balloon)
num = nums.popleft()
if num > 0:
balloons.rotate(-num+1)
nums.rotate(-num+1)
else:
balloons.rotate(-num)
nums.rotate(-num)
1
results
1
[1, 4, 5, 3, 2]
1