[PS] Swift에서 Queue 구현하기(Feat.백준 18258 시간초과 이슈..)

스위프트에서의 Queue

스위프트는 Queue라는 자료구조를 지원하지 않기 때문에, PS를 위해서 직접 구현해줘야 할 때가 있다. 효율적인 형태의 큐를 직접 구현해보자!

스택의 경우에는 스위프트 기본 제공 자료구조인 Array의 popLast() 메서드를 이용해서 시간복잡도 O(1)으로 간단히 구현할 수 있지만, queue에서 필요한 dequeue()에 사용할만한 메서드인 removeFirst()가 시간복잡도 O(N)인 관계로 커스텀 큐를 구현해줘야 한다!

 

스위프트를 이용한 Queue 구현 아이디어에는 크게 4가지가 있다.

1. 고전적인 방식으로 링크드 리스트 사용하기 : 공간복잡도가 좋지 않고, 접근성이 좋지 않음

2. Ring Buffer를 이용하기 : 정적 배열을 사용해야 하기 때문에 입력 받을 크기를 모른다면 사용하기 어려움

3. 더블 스택 이용하기 : 두 개의 스택(array)을 이용해 간단히 구현 가능!

4. 포인터 이용하기 : index를 이동하는 Int형 변수를 하나 두고 간단히 구현 가능!

 

이중에서 3번째 방법인 double stack을 이용하여 generic한 queue를 구현하려고 한다. 시간복잡도, 공간복잡도 측면에서 훌륭한 방법이다! 기본적으로 백준 18258번의 시간초과 이슈를 해결하기 위해 custom queue를 구현하려고 했기 때문에, 문제에서 제시하는 기능들을 protocol로 작성하여 struct를 구현하고자 한다.

Queue 프로토콜 작성

protocol Queue {
  associatedtype element
  
  var isEmpty: Bool { get }
  var size: Int { get }
  var first: element? { get }
  var last: element? { get }
  
  mutating func enqueue(element: element)
  mutating func dequeue() -> element?
}

Double Stack을 이용한 Queue 구현하기

위의 프로토콜을 따르는 queue를 구현하려고 한다. 그렇다면 어떤 식으로 2개의 스택을 이용할 수 있을까?

 

기본적인 아이디어는 enqueue에 필요한 스택 하나, dequeue에 필요한 스택을 하나 이용하는 것이다. popLast()와 reverse()의 시간복잡도가 O(1)이기 때문에 유효한 아이디어이다.

 

size : 당연히 size를 묻는다면 두 개의 스택에 존재하는 모든 원소의 갯수를 반환해야 한다

isEmpty : 두 스택이 모두(&&) 빈 경우에 true이다

first : dequeueStack은 dequeue해야 할 원소가 가장 뒤에 있는 구조이다. 따라서 dequeue에 원소가 있는지 확인하고, 있으면 dequeStack의 첫 원소를, 없다면 enqueueStack의 마지막 원소를 리턴한다.

last : first의 반대로 진행하면 된다.

enqueue() : 단순하게 enqueStack에 append하는 식으로 진행한다.

dequeue() : dequeueStack이 비어있는지 확인하고, 비었다면 enqueueStack의 모든 원소를 뒤집어서 dequeueStack에 옮겨 넣어준다. 그리고 popLast()를 이용하면 O(1)의 방식으로 dequeue()를 구현할 수 있다.

struct doubleStackQueue<T>: Queue {
  typealias element = T
  
  private var enqueueStack = [T]()
  private var dequeueStack = [T]()
  
  var size: Int {
    return enqueueStack.count + dequeueStack.count
  }
  
  var isEmpty: Bool {
    return enqueueStack.isEmpty && dequeueStack.isEmpty
  }
  
  var first: T? {
    guard !isEmpty else { return nil }
    return dequeueStack.isEmpty ? enqueueStack.first : dequeueStack.last
  }
  
  var last: T? {
    guard !isEmpty else { return nil }
    return enqueueStack.isEmpty ? dequeueStack.first : enqueueStack.last
  }
  
  mutating func enqueue(element: T) {
    enqueueStack.append(element)
  }
  
  mutating func dequeue() -> T? {
    guard !isEmpty else { return nil }
    
    if dequeueStack.isEmpty {
      dequeueStack = enqueueStack.reversed()
      enqueueStack.removeAll()
    }
    
    return dequeueStack.popLast()
  }
}

위와 같이 double Stack을 이용해서 queue를 구현했다.

let commandCount = Int(readLine()!)!
var customQueue = doubleStackQueue<Int>()
var res = ""

for _ in 0...commandCount-1 {
  receiveCommand()
}

func receiveCommand() {
  let commandArray = readLine()!.split(separator: " ").map { String($0) }
  judgeCommand(commandArray: commandArray)
}

print(res)

func judgeCommand(commandArray: [String]) {
  let command = commandArray.first
  switch command {
  case "push":
    let inputNumber = Int(commandArray[1])!
    customQueue.enqueue(element: inputNumber)
  case "pop":
    if let lastElement = customQueue.dequeue() {
      res += String(lastElement)
      res += "\n"
    } else { res += "-1\n" }
  case "size":
    res += String(customQueue.size)
    res += "\n"
  case "empty":
    if customQueue.isEmpty {
      res += "1\n"
    } else {
      res += "0\n"
    }
  case "front":
    if let firstElement = customQueue.first {
      res += String(firstElement)
      res += "\n"
    } else { res += "-1\n" }
  case "back":
    if let lastElement = customQueue.last {
      res += String(lastElement)
      res += "\n"
    } else { res += "-1\n" }
  default: print("Error")
  }
}

위와 같이 구현한 자료구조를 이용해 문제를 풀었더니 시간초과가 나왔다!

array를 이용했을 때보다 시간이 큰 폭으로 줄었지만, input의 크기가 커지니 속도를 감당하지 못했다.

 

이는 swift 언어가 입출력 속도가 느리기 때문에 일어난 현상이고, 구글링 결과 IO를 빠르게 해주는 클래스를 찾았다. 적용 결과 및 코드는 아래에 나와 있다.

 

제네릭한 형식으로 큐를 구현하니 그렇지 않을 때보다 타입캐스팅 등의 문제로 10% 정도 속도가 느리게 나왔다!

최종 코드 ( Fast File IO 클래스 적용 )

final class FileIO {
  private let buffer:[UInt8]
  private var index: Int = 0
  
  init(fileHandle: FileHandle = FileHandle.standardInput) {
    buffer = Array(try! fileHandle.readToEnd()!)+[UInt8(0)] // 인덱스 범위 넘어가는 것 방지
  }
  
  @inline(__always) private func read() -> UInt8 {
    defer { index += 1 }
    
    return buffer[index]
  }
  
  @inline(__always) func readInt() -> Int {
    var sum = 0
    var now = read()
    var isPositive = true
    
    while now == 10
            || now == 32 { now = read() } // 공백과 줄바꿈 무시
    if now == 45 { isPositive.toggle(); now = read() } // 음수 처리
    while now >= 48, now <= 57 {
      sum = sum * 10 + Int(now-48)
      now = read()
    }
    
    return sum * (isPositive ? 1:-1)
  }
  
  @inline(__always) func readString() -> Int {
    var str = 0
    var now = read()
    
    while now == 10 || now == 32 { now = read() } // 공백과 줄바꿈 무시
    
    while now != 10,
          now != 32,
          now != 0 {
      str += Int(now)
      now = read()
    }
    
    return str
  }
}

let reader = FileIO()
var customQueue = doubleStackQueue<Int>()
var res = ""

for _ in 0...reader.readInt()-1 {
  receiveCommand()
}

func receiveCommand() {
  let cmd = reader.readString()
  judgeCommand(command: cmd)
}

print(res)

func judgeCommand(command: Int) {
  switch command {
  case 448:
    customQueue.enqueue(element: reader.readInt())
  case 335:
    if let lastElement = customQueue.dequeue() {
      res += String(lastElement)
      res += "\n"
    } else { res += "-1\n" }
  case 443:
    res += String(customQueue.size)
    res += "\n"
  case 559:
    if customQueue.isEmpty {
      res += "1\n"
    } else {
      res += "0\n"
    }
  case 553:
    if let firstElement = customQueue.first {
      res += String(firstElement)
      res += "\n"
    } else { res += "-1\n" }
  case 401:
    if let lastElement = customQueue.last {
      res += String(lastElement)
      res += "\n"
    } else { res += "-1\n" }
  default: print("Error")
  }
}

---

참고한 자료

https://the-brain-of-sic2.tistory.com/entry/%ED%81%90

https://thoonk.tistory.com/61

https://gist.github.com/JCSooHwanCho/30be4b669321e7a135b84a1e9b075f88#file-usage-swift