[Swift] 백준2164

import Foundation

/// 카드는 1 ~ N까지 번호 붙어있음
/// 1번 카드가 제일 위, N번카드가 제일 아래
/// 아래 사항을 반복
/// 1. 제일 위의 카드를 바닥에 버림
/// 2. 제일 위의 카드를 제일 아래 카드 밑으로 옮김
/// 마지막으로 남게되는 카드는 뭐냐?

let N = Int(readLine()!)!

var cards = Array(1...N)

var queue = Queue<Int>()

for i in 1...N {
    queue.enqueue(i)
}

while queue.count >= 2 {
    
    queue.dequeue()
    if let dequeue = queue.dequeue() {
        queue.enqueue(dequeue)
    }
}

print(queue.dequeue()!)

struct Queue<T> {
    private var queue: [T?] = []
    private var head: Int = 0
    
    public var count: Int {
        return queue.count
    }
    
    public var isEmpty: Bool {
        return queue.isEmpty
    }
    
    public mutating func enqueue(_ element: T) {
        queue.append(element)
    }
    
    @discardableResult
    public mutating func dequeue() -> T? {
        guard head <= queue.count, let element = queue[head] else { return nil }
        queue[head] = nil
        head += 1
        
        if head > (count / 4) {
            queue.removeFirst(head)
            head = 0
        }
        return element
    }
}

시간복잡도가 O(1)인 queue를 사용하여 해결했다.