백준 2164 -swift(queue구조)

이번 문제는 굉장히 문제의 이해는 쉽다. N장의 카드가 있을때 1반카드가 가장 위, N번이 가장 아래로 가있는 스택구조인데 한번 진행될때마다 가장 위에 있는것을 버리고 그 밑에 있는 것을 가장 아래로 보내는 형태이다. 그렇게 마지막 카드 한장을 구하는 문제인데 이 문제를 읽자마자 큐 구조를 생각했다. 가장 위에 있는것을 빼서 가장아래로 놓기 위해서이다. 하지만 swift에서는 python과 달리 queue를 지원해주지 않는다. 왜지?

---

그래서 removeFirst()를 이용하여 앞에서부터 빼주고 append로 다시 뒤에 추가하는 형태로 짜려하였다. 하지만 이방법의 문제점은 removeFirst()를 해주게 되면 한칸씩 앞으로 땡겨지면서 결국 시간복잡도가 n이 되어버린다.

배열은 냅두고 배열의 위치를 가리키는 포인터를 바꿔보자!

이렇게 되면 deque를 한다면 그 가리키는 포인터를 뒤로 한칸씩 미루게 되면 배열을 땡겨오는 시간복잡도가 생기지 않는다. 결국 O(1)이 되어버린다.

struct Queue<T>{
  private var qu : [T?] = [] //deque되었을때 nil로 설정하기 위해
  private var point : Int  = 0
  public var count : Int {
    return qu.count - point
  }
  public var isEmpty : Bool {
    return count == 0 
  }
  public mutating func enqueue(_ element : T){
    qu.append(element)
  }
  public mutating func dequeue() -> T{
    guard point <= qu.count, let element = qu[point] else {return}
    qu[point] = nil 
    point += 1
    //너무 많이 nil이 쌓이게 되면 메모리 낭비이므로 어느정도 이상이면 앞부분에서 빼준다. 
    if( qu.count>100){
      qu.removeFirst(point)
      point = 0 
    }
    return element
  }
}

그런데 여기서 생기는 문제점! dequeue할때마다 nil로 설정한다는 것인데 메모리 낭비가 생기고, 어느 시점에 초기화를 해주어야 하는지 문제가 생긴다.

---

reversed()의 시간복잡도가 O(1)이라고 한다. 그래서 새로운 방법이 있다는 것을 알았다. 두개의 배열을 이용하는 것인데 하나는 추가용이고 하나는 dequeue용이다.

class Queue<T>{
  var enqueue : [T]
  var dequeue : [T] = []
  var count : Int {
    return enqueue.count + dequeue.count
  }
  var isEmpty : Bool {
    return enqueue.isEmpty && dequeue.isEmpty
  }
  init(_ queue: [T]){
    self.enqueue = queue
  } 
  func push(_ element : T){
    enqueue.append(element)
  }
  func pop() -> T {
    //dequeue배열이 비어있을경우 enqueue를 뒤집어주면 우리가 원하는 작업을 시간복잡도를 최소화하여 가능해진다.
    if(dequeue.isEmpty){
      dequeue = enqueue.reversed()
      enqueue.removeAll()
    }
    return dequeue.popLast()!
  }
}
let a = Int(readLine()!)!
var lista : [Int] = []
var count = 0
for i in 1...a{
  lista.append(i)
}
var myQueue = Queue<Int>(lista)
for _ in 1 ..< a{
    let _ = myQueue.pop()
    myQueue.push(myQueue.pop())
}
print(myQueue.pop())

최종본!! ㅊ