오늘은 LeetCode 232번 문제 "Implement Queue using Stacks"를 풀었다. 스택만 사용해서 큐를 구현하는 문제였는데, 처음에는 간단해 보였지만 효율적인 구현 방법에서 많은 배움이 있었다.
문제 링크: https://leetcode.com/problems/implement-queue-using-stacks/description/
첫 번째 접근: 단순한 배열 사용
처음에는 단일 배열을 사용하여 큐처럼 동작하게 구현하려 했다. push로 요소를 추가하고 pop으로 첫 번째 요소를 제거하는 방식이었다.
class MyQueue {
private var array: [Int] = []
init() {}
func push(_ x: Int) {
array.append(x)
}
func pop() -> Int {
return array.removeFirst()
}
func peek() -> Int {
return array.first!
}
func empty() -> Bool {
return array.isEmpty
}
}너무 쉽게 풀려서 이게 뭐지 하고 있었다. 하지만 너무 이상해서 다시 살펴보니 이 방식은 문제의 요구사항을 만족하지 못했다. 스택만 사용해야 했기 때문이다. 또한 removeFirst()는 O(n) 연산으로 매우 비효율적이었다.
removeFirst()가 O(n)인 이유
여기서 잠시 removeFirst()가 왜 O(n)인지 생각해봤다. 배열에서 첫 번째 요소를 제거하면 나머지 모든 요소가 한 칸씩 앞으로 이동해야 하기 때문이다. 이 이동 작업은 요소 개수에 비례하는 O(n) 시간이 필요하다. 예를 들어 [1, 2, 3, 4, 5]에서 첫 번째 요소를 제거하면, 2, 3, 4, 5가 각각 한 칸씩 앞으로 이동해야 한다. 배열 크기가 커질수록 이 작업의 비용은 더욱 커진다.
두 번째 시도: 두 개의 스택 활용
문제를 다시 읽고 두 개의 스택을 사용한 접근법으로 변경했다. 핵심은 push에 사용하는 스택과 pop/peek에 사용하는 스택을 분리하는 것이었다.
class MyQueue {
private var pushStack: [Int] = []
private var popStack: [Int] = []
init() {}
func push(_ x: Int) {
pushStack.append(x)
}
func pop() -> Int {
if popStack.isEmpty {
transferElements()
}
return popStack.popLast()!
}
func peek() -> Int {
if popStack.isEmpty {
transferElements()
}
return popStack.last!
}
func empty() -> Bool {
return pushStack.isEmpty && popStack.isEmpty
}
private func transferElements() {
while !pushStack.isEmpty {
popStack.append(pushStack.popLast()!)
}
}
}이 방법의 핵심은 push 연산에서는 항상 pushStack에 요소를 추가하고, pop이나 peek 연산에서는 popStack을 사용한다는 점이다. popStack이 비어 있을 때만 pushStack의 모든 요소를 popStack으로 옮기는데, 이때 스택의 선입후출(LIFO) 특성으로 인해 요소들의 순서가 자연스럽게 뒤집히게 된다. 이로써 큐의 선입선출(FIFO) 특성을 구현할 수 있다.
분할상환 분석(Amortized Analysis)이란?
이 문제를 풀면서 처음 접한 개념이 '분할상환 분석'이었다. 분할상환 분석은 연산들의 시퀀스에서 평균적인 성능을 측정하는 방법이다. 일부 연산이 비용이 크더라도, 그 비용을 여러 연산에 '분산'시켜 생각하는 것이다.
쉽게 말하면, 어떤 연산이 가끔 비용이 크더라도(예: O(n)), 그 연산이 자주 일어나지 않는다면 평균적으로는 훨씬 낮은 비용(예: O(1))으로 볼 수 있다는 개념이다.
두 스택 구현에서 pop이 분할상환 O(1)인 이유
두 스택 구현에서 pop 연산은:
1. 대부분의 경우: popStack에서 바로 요소를 꺼내므로 O(1)
2. 가끔(popStack이 비었을 때): pushStack의 모든 요소를 popStack으로 옮기는 O(n) 작업 필요
언뜻 보면 최악의 경우 O(n)이지만, 중요한 점은 각 요소는 최대 한 번만 pushStack에서 popStack으로 이동한다는 것이다.
예를 들어, n개의 요소에 대해 push n번, pop n번을 수행한다고 하자:
- push 연산은 항상 O(1)이므로 총 O(n) 시간
- pop 연산은 최초에 한 번 O(n) 이후로는 모두 O(1)이므로 O(n) + O(n-1) = O(2n-1) 시간
따라서 총 시간 복잡도는 O(n) + O(2n-1) = O(3n-1) = O(n)이 된다. 이를 연산 횟수 2n으로 나누면 각 연산당 평균 O(1) 시간이 나온다. 이것이 바로 분할상환 O(1)이다.
두 가지 접근법 비교
LeetCode 문제 설명에서는 두 가지 다른 접근법을 제시했다:
1. Approach #1: push가 O(n), pop이 O(1)
- push할 때마다 모든 요소를 뒤집어서 스택 바닥에 새 요소 추가
- 장점: pop이 항상 빠름
- 단점: push가 항상 느림
- Approach #2: push가 O(1), pop이 분할상환 O(1)
- push는 단순히 스택에 추가
- pop할 때 필요하면 한 번에 모든 요소 이동
- 장점: push가 항상 빠르고, pop은 평균적으로 빠름
- 단점: 가끔 pop이 느릴 수 있음
내가 구현한 방식은 두 번째 접근법으로, 일반적으로 더 효율적인 것으로 알려져 있다. 특히 push 연산이 pop보다 더 자주 일어나는 시나리오에서 유리하다.
성능 분석 결과
| 연산 | 시간 복잡도 | 설명 |
|---|---|---|
| push | O(1) | 스택의 맨 위에 요소 추가 |
| pop | 분할상환 O(1) | 대부분 O(1), 가끔 O(n) |
| peek | 분할상환 O(1) | pop과 동일한 로직 |
| empty | O(1) | 두 스택이 모두 비었는지 확인 |
pop과 peek 연산은 대부분의 경우 O(1)이지만, popStack이 비어있을 때 transferElements 함수가 호출되면 O(n) 시간이 소요된다. 하지만 각 요소는 최대 한 번만 pushStack에서 popStack으로 이동하므로, 분할상환 분석에서는 이 연산들이 O(1)이 된다.
오늘의 교훈
오늘의 문제 해결을 통해 배운 점은:
1. 자료구조의 특성을 활용하는 방법. 두 개의 스택을 사용하여 큐의 동작을 모방할 수 있다는 점이 인상적이었다.
2. 분할상환 분석의 중요성. 일부 연산이 간혹 비용이 크더라도, 평균적으로는 효율적일 수 있다는 개념이 매우 실용적이다.
3. Swift의 배열 메서드 특성 이해. popLast()가 O(1)인 반면 removeFirst()는 O(n)이라는 차이를 정확히 이해하고 활용하는 것이 중요하다.
4. 최적화 트레이드오프 고려. 자료구조 선택 시 어떤 연산을 최적화할지 고려해야 한다. 모든 연산을 동시에 최적화하기는 어렵다.
LeetCode 문제를 통해 이론적으로만 알고 있던 내용을 실제로 구현해보니 훨씬 더 깊게 이해할 수 있었다. 특히 분할상환 분석이라는 새로운 개념을 배운 것은 매우 큰 수확이었다. 앞으로도 다양한 자료구조 문제를 풀면서 실력을 키워나가야겠다.
