Posts 풍선 터뜨리기 [Python]
Post
Cancel

풍선 터뜨리기 [Python]

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
This post is licensed under CC BY 4.0 by the author.

나는야 포켓몬 마스터 이다솜 [Python]

가운데를 말해요 [Python]

Comments powered by Disqus.