프로그래머스 - 두 큐 합 같게 만들기 (2022카카오 테크 인턴쉽) 시간초과 해결

 

시간초과 발생 코드

아래대로 구현한다면 로직은 맞지만 시간초과가 발생합니다.

이유는 removeFirst() 로 처리하기에는 시간복잡도가 허용하지 않기 때문입니다. removeFirst() 를 사용하게 되면 첫번째 값을 뺀 다음 뒤에있는 모든 값들을 모두 한칸씩 앞으로 땡겨야하는 부담이 발생하기 때문에 로직은 간단해질 수 있지만 성능적인 면은 조금 떨어집니다.

func solution(_ queue1:[Int], _ queue2:[Int]) -> Int {
    var cnt = 0
    
    var q1 = Queue()
    queue1.forEach { value in
        q1.enqueue(value)
    }
    var q2 = Queue()
    queue2.forEach { value in
        q2.enqueue(value)
    }
    
    while q1.total != q2.total {
        var num = 0
        if q1.total > q2.total && !q1.isEmpty() {
            num = q1.dequeue()
            q2.enqueue(num)
        } else {
            if !q2.isEmpty() {
                num = q2.dequeue()
                q1.enqueue(num)
            }
        }
        cnt += 1
        
        if (q1.queue == queue1 && q2.queue == queue2) || q1.isEmpty() || q2.isEmpty() {
            return -1
        }
    }
    
    
    return cnt
}

struct Queue {
    var queue: [Int] = []
    var total: Int = 0
    
    mutating func enqueue(_ n: Int) {
        queue.append(n)
        total += n
    }
    
    mutating func dequeue() -> Int {
        total -= queue.first!
        return queue.removeFirst()
        
    }
    
    func isEmpty() -> Bool {
        return queue.isEmpty
    }
}

 

시간초과 문제해결 코드

시간초과 문제를 해결하기 위해서는 index 를 따로 저장하는 방법을 사용할 수 있습니다. 

import Foundation

func solution(_ queue1:[Int], _ queue2:[Int]) -> Int {
    
    let totalSum = queue1.reduce(0, +) + queue2.reduce(0, +)
    if totalSum % 2 != 0 {
        return -1
    }
    let targetSum = totalSum / 2
    
    var cnt = 0
    var q1 = queue1
    var q2 = queue2
    
    var total1 = q1.reduce(0, +)
    var total2 = q2.reduce(0, +)
    
    var q1_Index = 0
    var q2_Index = 0
    
    while cnt <= queue1.count * 3 {
        if total1 == targetSum {
            return cnt
        }
        var num = 0
        if total1 > total2 {
            if q1_Index < q1.count {
                num = q1[q1_Index]
                q1_Index += 1
                q2.append(num)
                total1 -= num
                total2 += num
            }
        } else {
            if q2_Index < q2.count {
                num = q2[q2_Index]
                q2_Index += 1
                q1.append(num)
                total1 += num
                total2 -= num
            }
        }
        cnt += 1
        
        if (q1 == queue1 && q2 == queue2) || q1.isEmpty || q2.isEmpty {
            return -1
        }
    }
    
    return -1
}