[BOJ] 2164 - 카드2

문제

 

풀이 코드

struct Queue<T> {
    private var elements: [T] = []
    private var reverseElement: [T] = []

    public var size: Int {
        return elements.count + reverseElement.count
    }

    public mutating func push(_ element: T) {
        return elements.append(element)
    }

    public mutating func pop() -> T? {
        if reverseElement.isEmpty {
            reverseElement = elements.reversed()
            elements.removeAll()
        }
        return reverseElement.isEmpty ? nil : reverseElement.popLast()
    }
}

var queue = Queue<Int>()
let N = Int(readLine()!)!

for n in 1...N {
    queue.push(n)
}

while queue.size != 1 {
    queue.pop()
    if let item = queue.pop() {
        queue.push(item)
    }
}

print(queue.pop()!)

 

풀이 과정

그냥 Queue를 이용하여 풀면 될거 같았다.

큐를 이용해 간단하게 구현하였지만 시간초과가 발생했다.

그 이유는 removeFirst 때문인데 첫 요소를 제거하면 다음의 엘리먼트들을 앞으로 한칸씩 땡겨와야 하기 때문에 연산시간이 오래걸린다.

그래서 removeElement 라는 변수를 큐 구조체내에 따로 구현해 주고, reversed 를 통해 마지막 요소를 제거하도록 했더니 시간초과 문제가 해결 되었다.

 

알고리즘을 풀때 첫요소나 중간 요소를 제거하면 그만큼 연산시간이 오래 걸린다는것을 배웠다.