[Algorithm] Swift Queue(Dequeue) 알고리즘 구현 트러블슈팅 기록 - Queue 구현시 시간초과 에러가 발생한다면?

Swift Queue(Dequeue) 알고리즘 구현 트러블슈팅 기록 - Queue 구현시 시간초과 에러가 발생한다면?

 

Swift로 알고리즘 문제를 풀면서 큐 알고리즘 관련한 문제가 나올 때 배열을 이용하여 큐를 구현하곤 했었습니다. (Swift에서는 따로 Queue를 지원하지 않기에)

 

따라서 enqueue를 구현할 때는 append()를,

dequeue를 구현할 때에는 자연스레 removeFirst() 함수를 사용해주었습니다.

 

그런데 최근에 알고리즘 문제를 풀면서 위와 같은 큐 구현방법이 시간 복잡도 측면에서 효율적이지 않다는 것을 알게 되어 트러블슈팅을 기록하고, 효율적인 큐 구현 방법을 공부해보려 합니다 :( :(

 

 

⚠️ Swift에서 Queue(Dequeue) 알고리즘을 구현하며 마주한 시간초과 에러

2022 KAKAO TECH INTERNSHIP - 두 큐 합 같게 만들기 문제를 풀면서 시간초과 에러를 마주하게 되었습니다.

위 문제 풀이에서 시간초과가 발생할 수 있는 부분이 어디일까 코드를 한줄 한줄 짚어보니 큐의 원소를 빼내는 dequeue 구현부분이 문제가 될 수 있겠다고 생각이 들었습니다.

 

그래서 removeFirst() 함수의 공식문서를 살펴보니 removeFirst() 함수의 시간 복잡도는 O(N)이었습니다.

 

 

O(N)이면,, 다른 시간 복잡도들보다 괜찮은거 같은데,, 왜지? 라고 생각이 들었습니다만,,

queue 원소의 개수가 최대 300,000개라는 것을 그제서야 보게 되었습니다... ㅎㅎ ㅠ

앞으로는 제한사항부터 잘 보기..!

[제한사항]
• 1 ≤ queue1의 길이 = queue2의 길이 ≤ 300,000

 

이처럼 queue 원소의 개수가 최대 300,000개일 수 있기에 while문 안에서 사용되는 removeFirst로 인해 위 문제에서 최악의 경우 300,000 * 300,000 번 연산을 수행하며 시간 초과가 발생합니다. (아마도 27,28,29번 테케가 이 경우에 해당되는 것 같아요)

 

queue1.removeFirst() 
// while문 안에서 시간복잡도 O(N)을 가지기 때문에 -> 위 문제에서 최악의 경우 300,000 * 300,000번 연산하게 됨

 

 

[N의 크기와 허용 시간복잡도의 관계 참고하면 좋은 자료]

 

💡 removeFirst()가 O(N)의 시간복잡도를 갖는 이유

removeLast()와 달리 removeFirst()는 첫번째 원소를 삭제하기 때문에 원소 삭제 후 남은 원소들의 index를 앞으로 당겨주는 작업이 필요합니다. 따라서 O(N)의 시간복잡도를 갖게 됩니다.

배열의 특성상 배열의 끝에 원소를 삽입하는 append() 말고 특정 위치에 원소를 삽입하는 insert(at:) 또한 위와 같은 이유로 O(N)의 시간복잡도를 갖게 되겠죠 !

 

💡 그렇다면 효율적인 Dequeue를 위해서는?

포인터의 원리를 이용해볼 수 있습니다.

Queue의 시작 위치를 가리키는 pointer 변수를 두어서 dequeue를 할 때마다 시작 위치를 1씩 뒤로 옮겨줍니다.

<코드로 구현>

var queue: [Int?] = [0, 1, 2, 3, 4]
var pointer = 0

// dequeue
queue[pointer] = nil
pointer += 1

// 결과
// [nil, 1, 2, 3, 4]
// pointer -> 1을 가리킴

이렇게 포인터의 원리를 사용하여 dequeue를 해주면 시간복잡도가 O(1)이 되어 더 효율적인 dequeue를 수행할 수 있습니다!

 

 

시간초과 문제가 있었던 <두 큐 합 같게 만들기> 문제도 포인터의 원리를 이용해 변경해주어 문제를 해결할 수 있었는데요,

해당 문제에서는 큐를 2개 사용하고 있기 때문에 포인터의 원리를 응용하여 투포인터(포인터 변수가 두개!)를 사용해주었습니다 :)

 

func solution(queue1:[Int], queue2:[Int]) -> Int {
    var maxCnt = queue1.count * 4
    var queue = queue1 + queue2
    var pointer = (0, queue1.count)
    var queue1sum = queue1.reduce(0, +)
    var queue2sum = queue2.reduce(0, +)
    var ans = 0
    
    while queue1sum != queue2sum {
        if queue1sum >= queue2sum {
            queue1sum -= queue[pointer.0]
            queue2sum += queue[pointer.0]
            pointer.0 = pointer.0 + 1 > queue.count - 1 ? 0 : pointer.0 + 1
        } else {
            queue1sum += queue[pointer.1]
            queue2sum -= queue[pointer.1]
            pointer.1 = pointer.1 + 1 > queue.count - 1 ? 0 : pointer.1 + 1
        }
        
        ans += 1
        
        // 탈출조건
        if ans > maxCnt {
            return -1
        }
    }
    
    return ans
}

https://github.com/hwangJi-dev/swiftAlgorithm/issues/12

[Algorithm] 두 큐 합 같게 만들기 · Issue #12 · hwangJi-dev/swiftAlgorithm

 

 

앞으로 제한 사항을 잘 살펴보고, 시간초과를 방지하기 위해 효율적인 코드를 설계하도록 고민을 해야겠다고 느꼈습니다.

또, 앞으로 큐를 구현할 때 효율적인 dequeue를 위해 포인터의 원리를 사용해주어야겠습니다! 😊😊

 

 

 

<참고 자료>

https://developer.apple.com/documentation/swift/array/removefirst(_:) 

https://babbab2.tistory.com/84

https://iamcho2.github.io/2021/10/04/Swift-dequeue