[Programmers] 두 큐 합 같게 만들기 (Level 2)

문제 

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

프로그래머스

문제 요약

두 큐가 주어지고 두 큐의 원소 합이 같아질 때까지 pop과 push를 계속 하는 문제예요. 

같아진다면 같아질 때까지 pop한 개수를 count해서 리턴하고 만약 같아지지 않는다면 -1을 리턴합니다. 

이때 각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수를 구해야 합니다. 

풀이 

각 큐의 원소 합을 같게 만들기 위한 최적의 해는 문제의 예시를 생각해보면 구할 수 있어요.

queue1 = [3, 2, 7, 2]
queue2 = [4, 6, 5, 1]

 

queue1과 queue2의 합이 다음과 같이 14, 16이면 queue2의 원소 4를 queu1에 옮겨요.

queue1 = [3, 2, 7, 2, 4]
queue2 = [6, 5, 1]

queue1과 queue2의 합은 18, 12이고 이번엔 queue1의 원소 3을 queue2에 옮겨요.

queue1 = [2, 7, 2, 4]
queue2 = [6, 5, 1, 3]

이럼 queue1과 queue2의 원소 합이 15로 같아집니다. 

이 예시에서 원소가 옮겨가는 2번의 과정을 통해 큐의 원소 합이 높은 곳에서 낮은 곳으로 옮기는 패턴을 찾을 수 있어요.

 

하지만, queue1의 원소를 모두 queue2로 옮겼고 queue2의 원소를 모두 queue1으로 옮겼는데 각 큐의 원소합이 같아지지 않을 수 있어요.

위 과정을 queue1의 원소의 개수 x 2번 반복하면 queue1과 queue2의 원소는 바뀌게 되고 그 때까지 queue1과 queue2의 원소 합이 같아진 경우가 없다면 -1을 리턴하면 됩니다.

 

 

여기서 주의할 점은, 시간 초과가 날 경우입니다.

 

1. array의 removeFirst를 사용할 경우 O(N)이므로 시간 초과가 날 수 있어요.

해결방법: array의 원소를 지우지 않고, index를 올리면서 접근해서 해결하면 됩니다.

 

2. sum을 매 반복마다 다시 구하면 이 또한 O(N)이므로 시간 초과 날 수 있어요.

해결방법: sum 또한 매번 다시 구하지말고, 원소를 더하고 빼는 방식으로 해결할 수 있습니다. 

---

코드

import Foundation

func solution(_ queue1:[Int], _ queue2:[Int]) -> Int {
    var queue1: [Int] = queue1
    var queue2: [Int] = queue2

    var limit: Int = queue1.count * 2

    var index1: Int = 0
    var index2: Int = 0
    var sum1 = queue1.reduce(0, +)
    var sum2 = queue2.reduce(0, +)

    var count: Int = 0
    var flag: Bool = false
    while queue1.count <= limit {
        if sum1 == sum2 {
            flag = true
            break
        }

        if sum1 < sum2 {
            sum2 -= queue2[index2]
            sum1 += queue2[index2]
            queue1.append(queue2[index2])
            index2 += 1
        } else {
            sum1 -= queue1[index1]
            sum2 += queue1[index1]
            queue2.append(queue1[index1])
            index1 += 1
        }

        count += 1
    }

    return flag == false ? -1 : count
}

 

배운 점 

1. 다른 사람의 풀이를 보다 swift로 큐를 구현해서 푼 풀이를 봤다. 확실히 큐를 구현해서 푸니까 index로 헷갈리지 않고 더 코드가 깔끔해지는 것.. 같군여.. 구현한 큐를 가져와봤는데 이런 방법도 있다는 것을 알아둬야겠슴당 

final class SameQueue<T> {
    private var inset: [T] = []
    private var outset: [T] = []

    init(_ queue: [T]) {
        inset = queue
    }

    var count: Int {
        inset.count + outset.count
    }

    func enqueue(_ value: T) {
        inset.append(value)
    }

    func dequeue() -> T {
        if outset.isEmpty {
            outset = inset.reversed()
            inset.removeAll(keepingCapacity: true)
        }
        return outset.removeLast()
    }
}