[Swift] Queue 자료 구조 (removeFirst를 popLast로 대체하기)

[머릿말]

Swift를 사용하여 Programmers에서 여러 코딩테스트를 풀고 있다. 어느덧 5천대 순위가 되었고 이전에는 Queue를 사용하여 문제를 풀어도 통과가 되었지만 이제는 시간 초과 오류를 가끔씩 접하곤 한다. 이는 removeFirst() 메서드의 시간 복잡도가 O(n)이기 때문인데, 이를 시간 복잡도가 O(1)인 popLast() 메서드로 대체하면 실행 시간을 훨씬 단축시킬 수 있다.

---

1. 기존에 사용했던 Queue

Python에는 Queue가 존재해서 좋았지만 Swift에는 존재하지 않는다. 따라서 배열을 사용하여 직접 Queue를 만들어 사용해야 한다. 기존에 문제를 풀 때 사용했던 Queue는 아래와 같이 그냥 배열 그 자체였다.

// 기본 Queue
var queue: [Int] = []

// 값 추가
queue.append(1)
queue.append(2)
queue.append(3)

print(queue) // [1, 2, 3]

// 값 삭제
queue.removeFirst()

print(queue) // [2, 3]

 

1-1. removeFirst()의 시간 복잡도 O(n)

removeFirst() 메서드를 사용하여 Queue의 pop 기능을 사용해도 얼마든지 가능은 하다. 그러나 이 메서드는 첫 번째 원소를 삭제한 뒤 이후의 원소들을 모두 한 칸씩 앞으로 당겨와야 하는 작업이 필요하고, 이는 원소의 개수만큼의 시간이 걸리게 된다. 즉, O(n)의 시간 복잡도를 갖는 것이다. 이는 원소의 개수가 증가할수록 더 많은 실행 시간이 소요되는 문제가 따른다.

 

 

2. 이를 해결하기 위한 Queue 구조체

removeFirst() 메서드와 달리 popLast() 메서드는 맨 뒤에 있는 원소를 삭제하기만 하면 되기에 시간 복잡도는 O(1)밖에 되지 않는다. 이를 사용하면 실행 시간을 단축시킬 수 있다.

struct Queue<T> {
    var enqueue: [T] = []
    var dequeue: [T] = []
    
    // isEmpty
    var isEmpty: Bool {
        enqueue.isEmpty && dequeue.isEmpty
    }
    
    // push
    mutating func push(_ element: T) {
        enqueue.append(element)
    }
    
    // pop
    mutating func pop() -> T? {
        if dequeue.isEmpty {
            dequeue = enqueue.reversed()
            enqueue.removeAll()
        }
        return dequeue.popLast()
    }
}

var queue = Queue<Int>()
queue.push(1)
queue.push(2)
queue.push(3)

print(queue.pop()) // Optional(1)
print(queue.pop()) // Optional(2)
print(queue.pop()) // Optional(3)
print(queue.pop()) // nil

전체적인 형태는 위와 같다. 내용을 하나씩 살펴보면 다음과 같다.

 

2-1. struct Queue<T>

저장할 원소의 타입을 상황에 맞게 대응할 수 있도록 제너릭(Generic)을 사용하였다.

 

2-2. enqueue, dequeue

원소를 추가(push)할 때는 enqueue 배열을 사용하고, 원소를 꺼낼(pop) 때는 dequeue 배열을 사용한다.

 

2-3. push()

인스턴스의 값을 변경하는 메서드이므로 mutating 키워드를 사용하였다. 전달받은 값을 enqueue 배열에 추가한다.

 

2-4. pop()

이 역시 인스턴스의 값을 변경하는 메서드이므로 mutating 키워드를 사용하였다.

 

popLast() 메서드는 배열에 원소가 없을 수도 있으므로 옵셔널(Optional) 값을 반환한다. 따라서 pop() 메서드 역시 옵셔널 타입을 반환하도록 하였다.

 

원소를 꺼낼 때 사용한다 말했던 dequeue 배열이 비어있을 경우에는 값을 추가하는 것이 우선이므로, enqueue 배열의 값을 복사하는데 이때 popLast() 메서드를 사용하기 위해 enqueue 배열을 뒤집어서 복사한다.

 

enqueue 배열의 값이 dequeue 배열로 복사됐으므로 기존 enqueue 배열의 값은 더 이상 필요가 없다. 따라서 removeAll() 메서드를 사용하여 배열의 모든 값을 삭제한다.

 

이후 새롭게 추가되는 값은 다시 enqueue 배열에 추가되고, 값을 꺼낼 때는 dequeue 배열의 맨 뒤에서 꺼내지게 된다(O(1)).

 

 

---

학교에서 알고리즘을 처음 배울 때만 하더라도 시간 복잡도의 중요성을 간과했었다...🤣

그러나 계속해서 코테를 풀다보니 지금은 시간 복잡도를 따지며 코드를 작성하게 되었고, 코드를 작성할 때 더 생각하는 시간을 가지게 되는 것 같다👍🏻

 

끝!