[Swift] 프로그래머스 코딩테스트 연습>2022 KAKAO TECH INTERNSHIP > 두 큐 합 같게 만들기

 

시간 초과 문제를 해결하기 위해 고민을 많이 했다.

• queue의 합을 구하기 위해 reduce나 반복문을 사용하면 queue의 길이만큼 연산하게 되니O(n), 처음 queue의 합을 구하고 합에서 요소만큼 더하기 빼기 연산으로 하면 O(1)
• queue를 쓰게 되면 removeFirst(), append() 연산 할 때마다 시간 복잡도가 증가함O(n) -> queue 두 개를 합쳐서 dequeue 사용O(1)

 

 

 

import Foundation

func solution(_ queue1:[Int], _ queue2:[Int]) -> Int {
    var result = 0
    var sumQ1 = 0
    var sumQ2 = 0
    var dequeue = queue1 + queue2
    var dequeuelen = dequeue.count
    for i in 0..<queue1.count{
        sumQ1 += queue1[i]
        sumQ2 += queue2[i]
    }
    
    let halfNum = (sumQ1 + sumQ2) / 2
    if (sumQ2+sumQ1) % 2 != 0{
        return -1
    }
    var q1head = 0
    var q2head = queue1.count
    while result < queue1.count * 4{
        if sumQ1 == halfNum, sumQ2 == halfNum{
            return result
        }
        if sumQ1 > halfNum{
            let e = dequeue[q1head]
            sumQ1 -= e
            sumQ2 += e
            result += 1
            q1head += 1
        }
        
        if sumQ2 > halfNum{
            let e = dequeue[q2head]
            sumQ2 -= e
            sumQ1 += e
            result += 1
            q2head += 1
        }
        if q1head == dequeuelen{
            q1head = 0
        }
        if q2head == dequeuelen{
            q2head = 0
        }
    }
    return -1
}