[프로그래머스] 두 큐 합 같게 만들기

https://school.programmers.co.kr/learn/courses/30/lessons/118667

✍️ 첫번째 접근

먼저 하나의 queue의 합을 구하는 함수, queue의 합이 우리가 원하는 합을 넘는지 여부를 구하는 함수, 두 queue의 합이 같은지를 구하는 함수를 구현하였다.
두 queue의 합이 같은지를 구하는 함수인 isSame 함수로 인해 시간 초과가 발생한 거 같았다. 아마 변수를 계속해서 선언하기 때문에 메모리를 많이 잡아먹거나, 계속해서 queue의 합을 구하는 함수를 호출해서 등의 이유인 거 같다. 또한 test case2에서 실패인 이유는 isSame에서 0번 시도에 두 queue의 합이 같을 수 있는데 for문에서 i가 1부터 시작해서 그런 거 같다.

import Foundation

func queueSum(_ queue: [Int]) -> Int {   // 고차함수 시간 복잡도를 줄이기 위해 for문 사용
    var num: Int = 0
    for i in queue {
        num += i
    }
    return num
}

func overSum(_ queue: [Int], _ sum : Int) -> Bool {
    return queue.reduce(0,+) > sum ? true : false
}

func isSame(_ queue1: [Int], _ queue2: [Int], _ sum: Int, _ answer: [Int]) -> [Int] {
    print("앞 큐: \(queue1)\t뒤 큐: \(queue2)")
    var arr: [Int] = []
    for i in 1..<queue1.count {
        if let num = answer.min() {
            if i >= num {
                break
            }
        }
        var a = queue1
        var b = queue2
        var cnt: Int = i
        while cnt != 0 {
            b.append(a.first!)
            a.removeFirst()
            cnt -= 1
        }
        if queueSum(a) == sum {   // 하나의 큐가 sum이 되면 만족하므로
            arr.append(i)
            break
        }
        print("===a: \(a)\tb: \(b)===")
        let len = b.count - 1
        for j in 1...len {
            var aa = a
            var bb = b
            cnt = j
            while cnt != 0 {
                aa.append(bb.first!)
                bb.removeFirst()                
                cnt -= 1
            }
            if overSum(aa,sum) {
                break
            }
        print("aa: \(aa)\tbb: \(bb)")
            if queueSum(aa) == sum {   // 하나의 큐가 sum이 되면 만족하므로
                arr.append(i+j)     
                break
            }
        }
    }    
    return arr
}

func solution(_ queue1:[Int], _ queue2:[Int]) -> Int {
    var answer: [Int] = []
    let sum = (queueSum(queue1) + queueSum(queue2))/2   // (두 큐 합)/2
    answer += isSame(queue1,queue2,sum,answer)
    answer += isSame(queue2,queue1,sum,answer)
    

    
    return answer.min() ?? -1
}

✍️ 두번째 접근

결론적으로 각 queue의 합을 알아야 한다. 그러므로 각 queue의 합을 계속해서 구하지 않고 미리 각 queue의 합을 변수로 두고 각 합을 비교해가면서 두 큐의 합을 같게 만들 수 있다.
그리고 각 queue를 순회하는 과정에서 removeFirst()를 사용하여 시간 초과가 발생하였는데 이 시간 복잡도가 O(n)이므로, 굳이 큐에서 하나씩 삭제하지 않고 인덱스를 활용하여 시간 복잡도를 줄임으로써 문제를 해결하였다.

import Foundation

func solution(_ queue1:[Int], _ queue2:[Int]) -> Int {
    var queue1 = queue1
    var queue2 = queue2
    let len = queue1.count  // 맨 처음 큐의 길이
    var sum1 = queue1.reduce(0,+)
    var sum2 = queue2.reduce(0,+)
    var num: Int = 0
    var idx1: Int = 0
    var idx2: Int = 0
    if ((sum1+sum2) % 2 == 1) { // 두 큐의 합이 홀수라면 정확히 나눌 수 없으므로
        return -1
    }
    for i in 0..<len*3-2 {
        if queue1.isEmpty || queue2.isEmpty {
            return -1
        }
        if sum1 > sum2 {
            num = queue1[idx1]
            queue2.append(num)
            sum1 -= num
            sum2 += num
            idx1 += 1
        }
        else if sum1 < sum2 {
            num = queue2[idx2]
            queue1.append(num)
            sum1 += num
            sum2 -= num
            idx2 += 1
        }
        else {
            return i
        }
    }
    
    return -1
}