백준 2346번 풍선 터뜨리기 - SWIFT

문제

---

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은 적혀있지 않다.

 

출력

첫째 줄에 터진 풍선의 번호를 차례로 나열한다.

 

문제 링크

2346번: 풍선 터뜨리기

 

 

풀이

---

풍선이 이런 식으로 나열되어 있고, 각 풍선 안에는 숫자가 적힌 종이가 있다.▼

 

 

1번 부터 풍선을 터뜨리는데, 풍선을 터뜨리고 나온 종이에 있는 수만큼 칸을 이동해준다.▼

 

 

그리고 그 칸에 이동해서 똑같이 풍선을 터뜨리고, 나온 종이에 적힌 수만큼 칸을 이동해준다.

이미 터진 풍선은 스킵하고, 기본적으로 원 순환이라고 생각한다.▼

 

 

이 행위를 다 터뜨릴 때 까지 반복해주면 된다.

구현만 하면 되니까 간단하다.

문제 힌트로는 덱이라고 나와는 있는데, 기본적인 덱은 앞과 뒤만 제거가 가능하므로 그림처럼 중간을 제거하는 경우를 이용해야해서 덱을 이용해서 풀지는 않았다.

그래서 원형 큐에서 사용했던 순환 계산만 빼서 풀었다.

양수이면, 현재 인덱스 = 현재 인덱스 % 현재 풍선 갯수

음수이면, 현재 인덱스 = 현재 인덱스 % 현재 풍선 갯수 + 현재 풍선 갯수

로 계산을 해줘서 순환적으로 돌게 했다.

 

 

프로그램 동작

---

만약 풍선을 터뜨린다는 표현을 배열 요소의 삭제로 구현했다면 약간 난감한 상황이 생길 수 있다.

위의 그림에서는 풍선을 터뜨릴 때 그 자리를 남겨줬지만, 배열 요소의 삭제로 구현을 했다면 한 자리씩 밀려있게 된다.

일반 표현 ▼

 

 

실제 배열 ▼

 

 

이런 상황에서 터뜨린 번호를 출력하라고 하게 되면, 실제로는 5번을 터뜨렸다고 해도 프로그램은 3번을 터뜨렸다고 기억하게 된다.

그래서 풍선들을 저장할 때, 이 풍선이 몇 번이었는 지도 같이 저장을 해줘야 한다.

그러면 터뜨렸을 때, 실제로는 내가 몇 번을 터뜨렸는 지 알수 있게 된다.▼

 

 

Swift 코드

---

let N : Int
if let n = readLine() {
    N = Int(n) ?? 0
}
var balloon = readLine()!.split(separator: " ").enumerated().map{ ($0 ,Int(String($1))!) }
var index = 0
var answer = ""

while true {
    var tmp = balloon[index].1
    answer += "\(balloon[index].0 + 1) "
    if tmp > 0 { tmp -= 1 }
    balloon.remove(at: index)
    index += tmp
    if balloon.count == 0 { break }
    index = (index >= 0) ? index : balloon.count + index % balloon.count
    index %= balloon.count

}

print(answer)

 

자기 원래 번호를 저장하려면 for문으로 대입을 해줘야한다고 생각할 수 있지만, enumerated() 함수를 사용하면 배열 번호를 튜플값으로 같이 저장해준다.