2346번: 풍선 터뜨리기
1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선
www.acmicpc.net
문제
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은 적혀있지 않다.
출력
첫째 줄에 터진 풍선의 번호를 차례로 나열한다.
코드
n = int(input())
paper = list(map(int, input().split()))
balloon = []
for i in range(n):
balloon.append((i+1, paper[i])) # 풍선 번호, 종이에 적힌 숫자
idx = 0
while balloon:
idx %= len(balloon)
print(balloon[idx][0], end=" ")
next_idx = idx + balloon[idx][1] + (-1 if balloon[idx][1] > 0 else 0)
balloon.pop(idx)
idx = next_idx
balloon이란 배열에 (풍선 번호, 종이에 적힌 숫자)의 튜플 형태로 넣어서 문제를 풀었다.
인덱스 값과 pop() 함수를 이용하여 터뜨리는 풍선들을 배열에서 삭제해주었다.
인덱스 값의 범위가 balloon 배열을 벗어나면 안되므로 idx값을 매번 balloon 배열의 크기로 나누어주었다.
다음에 터뜨릴 풍선의 인덱스 값을 구할 때 주의해야할 점은 종이에 적힌 값이 양수라서 오른쪽으로 가야하는 경우라면 이번에 터진 풍선이 배열에서 삭제되므로 배열의 인덱스 값이 더 큰 쪽으로 갈 때는 1을 빼주어야 한다.
'문제풀이 > 자료구조' 카테고리의 다른 글
[Python/파이썬] 백준 10799번 쇠막대기 (0) | 2023.01.24 |
---|---|
[Python/파이썬] 백준 1874번 스택 수열 (0) | 2023.01.24 |
[Python/파이썬] 백준 1935번 후위 표기식2 (1) | 2023.01.22 |
[Python/파이썬] 백준 10866번 덱 (0) | 2023.01.22 |
[Python/파이썬] 백준 2164번 카드2 (0) | 2023.01.22 |