99클럽 코테 스터디 5일차 TIL - 두 개의 큐로 스택 구현하기

오늘은 LeetCode 225번 문제, “Implement Stack using Queues” 를 풀었다.

어제 풀었던 스택을 큐로 구현하는 문제의 반대 버전으로, 큐만 사용해서 스택을 구현하는 문제였다.
아휴 .. 또 문제를 제대로 읽지 않았다.

---

❌ 첫 번째 삽질: 문제 제대로 안 읽기

처음엔 문제를 제대로 읽지 않고 그냥 스택을 구현하라는 줄 알고, 아래와 같이 작성했다:

class MyStack {
    private var array: [Int]
    init() {
        self.array = .init()
    }

    func push(_ x: Int) {
        array.append(x)
    }

    func pop() -> Int {
        return array.removeLast()
    }

    func top() -> Int {
        return array.last ?? 0
    }

    func empty() -> Bool {
        return array.isEmpty
    }
}

당연히 정답은 맞았지만 틀린 것이었다.
문제의 핵심은 “큐만 사용해서 스택을 구현하라”는 것이었다.

---

✅ 두 개의 큐로 스택 구현하기

문제를 다시 읽고, 두 개의 큐를 사용하는 방식으로 접근했다.

핵심 아이디어는 다음과 같다:

1. queue1에 모든 요소를 저장한다.
2. pop 또는 top 연산 시, 마지막 요소를 제외한 나머지를 queue2로 이동시킨다.
3. 마지막에 남은 요소가 스택의 top.
4. 연산이 끝나면 queue1과 queue2를 교체해준다.

class MyStack {
    private var queue1: [Int] = []
    private var queue2: [Int] = []

    func push(_ x: Int) {
        queue1.append(x)
    }

    func pop() -> Int {
        while queue1.count > 1 {
            queue2.append(queue1.removeFirst())
        }
        let popped = queue1.removeFirst()
        swap(&queue1, &queue2)
        return popped
    }

    func top() -> Int {
        while queue1.count > 1 {
            queue2.append(queue1.removeFirst())
        }
        let top = queue1.removeFirst()
        queue2.append(top)
        swap(&queue1, &queue2)
        return top
    }

    func empty() -> Bool {
        return queue1.isEmpty
    }
}

---

📈 성능 분석

연산	시간 복잡도	설명
push	O(1)	큐의 뒤에 요소 추가
pop	O(n)	n-1개 요소를 이동하고 마지막 요소 제거
top	O(n)	n-1개 요소를 이동하고 마지막 요소를 다시 추가
empty	O(1)	비어 있는지 확인

---

⚠️ Swift에서 removeFirst()의 함정

오늘 복습하면서 다시 떠올랐던 중요한 사실:

• Swift의 Array.removeFirst()는 시간 복잡도 O(n) 이다.
• 내부적으로 모든 요소가 한 칸씩 앞으로 이동하기 때문.
• 즉, 위 구현에서 removeFirst()를 반복 호출하면 최악의 경우 O(n²) 시간 복잡도가 나올 수 있다.

---

💡 오늘의 교훈

• 제발 문제를 꼼꼼히 읽자. 요구사항을 정확히 이해하지 않으면 잘못된 방향으로 풀게 된다.
• 자료구조의 특성을 이해하자. 같은 동작도 다른 방법으로 구현할 수 있다.
• 연산의 효율성을 고려하자. 특히 Swift에서의 removeFirst()는 항상 조심할 것.
• 문제의 제약을 존중하자. 주어진 조건을 지키면서 최적의 방법을 고민하는 습관이 중요하다.

---

Swift로 알고리즘 문제를 풀 때는 단순히 동작만 맞추는 게 아니라, 언어의 성능 특성과 자료구조의 구현 방식까지 고려해야 한다는 걸 다시 한 번 느꼈다.