코딩테스트 연습 - 두 큐 합 같게 만들기

문제 풀이 아이디어

그리디 알고리즘

문제의 목적은 두 “큐”의 합을 같게 하는 것입니다. 한 큐의 합이 다른 큐의 합과 다른 경우 두 큐의 차이를 줄일 수 있는 방법은 큰 큐에서 pop한 수를 작은 큐에 push하는 방법 뿐입니다. 큐는 선입선출이므로 현재 큐에 다른 수가 들어와도 pop의 대상이 되는 수는 정해져있습니다. 작은 큐에서 먼저 pop하고 큰 큐에서 나중에 pop하는 꼼수(?)를 써보려고 해도 결국 그리디와 결과가 동일합니다.

따라서 큐 2개를 만들어놓고 두 큐의 합을 비교해서 그리디 알고리즘을 적용해서 풀겠습니다.

최대 시도 횟수

문제에서 주어진 테스트 케이스 중에 3번은 그리디 알고리즘을 적용할 경우 무한 루프에 빠지는 케이스입니다. 이런 경우를 방지하기 위해서 최대 시도 횟수를 정해주어야 합니다.

논리적으로 생각을 해보면 그리디 알고리즘을 적용하다가 큐1과 큐2이 완전히 뒤바뀌었다가 다시 한번 완전히 뒤바뀌어서 초기 상태로 돌아오면 이 이후는 같은 과정을 반복하면서 무한 루프에 빠진다고 볼 수 있습니다.

큐1과 큐2의 길이의 합만큼 반복하면 완전히 뒤바뀌고 다시 그만큼 반복하면 다시 초기 상태로 돌아옵니다. 두 큐의 길이는 같으므로 최대 시도 획수는 (큐1의 길이) * 4가 됩니다.

여러 블로그를 참고해봤는데요. (큐1의 길이) 2를 해도 대부분의 테스트케이스를 통과하고 (큐1의 길이) 3이면 모든 테스트 케이스를 통과한다고 합니다. 다만 왜 그런지 설명할 수는 없을 것 같습니다. 시간초과의 걱정은 없으므로 안전빵(?)으로 *4를 하도록 하겠습니다.

reduce는 O(N)

처음에 풀 때 reduce를 통해서 매번 합을 구했더니 무수한 시간초과가 뜨더라구요. reduce의 시간복잡도는 O(N)입니다. (N은 배열의 길이) 반복문에서 사용하기에는 무거운 메소드입니다. 각각의 큐의 합을 별도의 변수로 선언해두고 +/-해서 사용하면 O(1)으로 줄일 수 있습니다.

코드

// Swift로 Queue 구현하기
struct Queue {
    private var index: Int = 0
    private var array: [Int]

    init(array: [Int]) {
        self.array = array
    }

    var count: Int {
        return array.count - index
    }
    
    mutating func push(_ num: Int) {
        array.append(num)
    }

    mutating func pop() -> Int {
        defer {
            index += 1
        }
        return array[index]
    }
}

func solution(_ queue1:[Int], _ queue2:[Int]) -> Int {
        
    // 각각 queue의 초기 합
    var sum1 = queue1.reduce(0, +)
    var sum2 = queue2.reduce(0, +)
    
    // 합이 홀수이면 -1
    guard (sum1 + sum2) % 2 == 0 else { return -1 }

    var queue1 = Queue(array: queue1)
    var queue2 = Queue(array: queue2)

    // 최대 수행 횟수
    let limit = queue1.count * 4
    // 정답
    var ans = 0

    // 반복문
    while sum1 != sum2 && ans < limit {
        // queue1이 더 큰 경우: queue1 pop -> queue2 push
        if sum1 > sum2 {
            let popped = queue1.pop()
            queue2.push(popped)
            sum1 -= popped
            sum2 += popped
        // queue2가 더 큰 경우: queue2 pop -> queue1 push
        } else {
            let popped = queue2.pop()
            queue1.push(popped)
            sum1 += popped
            sum2 -= popped
        }
        ans += 1
    }

    // 반복문을 수행한 결과 합을 동일하게 만들었다면 ans를 아니면 -1을 리턴
    return sum1 == sum2 ? ans : -1
}