2346번: 풍선 터뜨리기

🤔어떻게 풀어야 할까?

/*
 # 써야할 자료구조 = deque
     : 원 & 회전을 구현하기 위해서는 Deque를 시용하는 것이 좋습니다.
     : 왼쪽으로 가는 연산의 경우 popRight -> pushleft로 구현할 수 있습니다.

 # 문제 풀이 아이디어
     : 풍선의 번호들을 deque로 받습니다.
     : 풍선의 맨 처음 위치를 기억해야 하니까 enumerated를 활용해서 (원래 풍선 순서, 쪽지숫자)의 튜플로 받습니다.
     : popleft로 풍선 터뜨립니다. (일단 터뜨리고 나서 숫자를 센다고 했으므로)
     : 풍선 안에 있는 번호에 맞게 회전합니다.
     : dq의 길이가 0일 때까지 반복합니다.

 # 의사코드
     1. 인풋을 받습니다.
     2. while문으로 반복합니다.
         2-1. 일단 popleft해서 터뜨리고 풍선 위치는 배열에 저장합니다.
         2-2. 쪽지 숫자만큼 반복문 실행
             2-2-1. 양수의 경우 (n - 1)회 popLeft -> pushRight
             2-2-2. 음수의 경우 abs(n)회 popRight -> pushLeft
     3. joined을 활용해서 배열을 양식에 맞게 출력합니다.

 # 시간복잡도
     : while 반복문이 n번 반복됩니다.
     : 내부에서 풍선 위치 이동을 최대 n번 반복합니다. (dq 연산은 O(1))
     : O(n**2)이고 n이 1000이므로 시간 내에 풀이가 가능합니다.
 */

풀이

struct Deque<T> {
    var input = [T]()
    var output = [T]()

    var count: Int {
        return input.count + output.count
    }

    mutating func pushLeft(_ n: T) {
        output.append(n)
    }

    mutating func pushRight(_ n: T) {
        input.append(n)
    }

    mutating func popLeft() -> T {
        if output.isEmpty {
            output = input.reversed()
            input.removeAll()
        }
        return output.popLast()!
    }

    mutating func popRight() -> T {
        if input.isEmpty {
            input = output.reversed()
            output.removeAll()
        }
        return input.popLast()!
    }
}

// Balloon의 typealias 선언
typealias Balloon = (index: Int, next: Int)

// 입력 받기
let N = Int(readLine()!)!
var input = readLine()!.split(separator: " ").map { Int(String($0))! }

// 큐 선언
var balloons = Deque<Balloon>()

// enumerated를 활용해서 풍선의 원래 위치 + 쪽지에 적힌 값을 튜플로 저장
for (index, next) in input.enumerated() {
    balloons.pushRight((index: index + 1, next: next))
}

// 터진 풍선을 순서대로 담을 배열
var result = [Int]()

// 터진 풍선을 저장할 변수
var balloon: Balloon

// 풍선 터뜨리기
while true {
    balloon = balloons.popLeft() //👉 deque의 맨앞에 있는 풍선을 터뜨린다.
    result.append(balloon.index) //👉 결과에 저장
    if balloons.count == 0 { break } //👉 queue가 비었으면 break
    
    //✅ 터뜨려야 할 풍선을 deque의 맨 앞으로 이동한다.
    if balloon.next > 0 {
        for _ in 0..<(balloon.next - 1) {
            balloons.pushRight(balloons.popLeft())
        }
    } else {
        for _ in 0..<abs(balloon.next) { //👉 터뜨릴 풍선을 deque의 맨앞까지 옮기기 위해서는 양수보다 1번 더 반복!
            balloons.pushLeft(balloons.popRight())
        }
    }
}

// 결과 출력
print(result.map { String($0) }.joined(separator: " "))