[Swift] 백준_Router(15828)

문제

 

https://www.acmicpc.net/problem/15828

15828번: Router

 

 

풀이

 

스위프트에서는 큐가 구현되어있지 않아서 따로 구현해야한다. 배열을 그대로 이용하는 방법도 있지만 removeFirst()때문에 O(n)이 될 수 밖에 없어 두 스택으로 구현해서 사용했다.

reversed()가 O(1)이기때문에 시간복잡도가 더 낮기 때문에 시간이 더 빠를 것이다.

 

0인 경우, rightQueue가 비어있다면 left를 뒤집어서 넣은 뒤에 removeLast()를 이용해서 버퍼에서 제거해주었다. rightQueue에 left에 들어있던 원소들이 있고 left는 빈 상태일 것이다. 이후의 append하는건 left에 그대로 넣어주면 뒤집어진 right + left가 queue가 될 것이다.

import Foundation

let n = Int(readLine()!)!
var leftQueue: [String] = []
var rightQueue: [String] = []

while true {
    let number = readLine()!
    if number == "-1" {
        break
    }
    if number == "0" {
        if rightQueue.isEmpty {
            rightQueue = leftQueue.reversed()
            leftQueue.removeAll()
        }
        rightQueue.removeLast()
    } else {
        if leftQueue.count + rightQueue.count != n {
            leftQueue.append(number)
        }
    }
}
let result = rightQueue.reversed() + leftQueue
print(result.joined(separator: " "))

 

_____________________________________________________________________________________________________

 

큐를 이용할땐 위와 같은 방법으로 생각해보자.