[Algorithm] 두 큐 합 같게 만들기

[hwangJi-dev]

📌 TODO

• 문제 풀이
• 정리

🎢 두 큐 합 같게 만들기

💬 문제

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

💬 Idea

1. 첫번째 아이디어
   1. 배열을 queue로 사용해서 queue1, queue2의 각 합계를 비교한다
   2. 합계가 더 큰쪽에서 작은쪽으로 원소를 이동시킨다
2. 두번째 아이디어
   1. 투포인터를 사용한다.
   2. 원리는 1과 같다.

💬 풀이

1️⃣ <1차 풀이>

func solution(_ queue1:[Int], _ queue2:[Int]) -> Int {
    var queue1 = queue1
    var queue2 = queue2
    var ans = 0
    
    while queue1.reduce(0, +) != queue2.reduce(0, +) {
        let queue1sum = queue1.reduce(0, +) 
        let queue2sum = queue2.reduce(0, +) 
        
        if queue1sum >= queue2sum {
            queue2.append(queue1.removeFirst())
            ans += 1
        } else {
            queue1.append(queue2.removeFirst())
            ans += 1
}
        
        // 탈출조건
        if queue1.isEmpty || queue2.isEmpty {
            return -1
        }
    }
    
    return ans
}

정확성 56.7 / 100.0

2️⃣ <2차 풀이>
-> 반복문 내에서 고차함수 reduce를 제외하여 sum(총합)을 계산하는 원리를 변경했다. → 시간초과 일부 해결

func solution(_ queue1:[Int], _ queue2:[Int]) -> Int {
    var queue1 = queue1
    var queue2 = queue2
    var queue1sum = queue1.reduce(0, +) 
    var queue2sum = queue2.reduce(0, +)
    var ans = 0
    
    while queue1sum != queue2sum {
        if queue1sum >= queue2sum {
            let remove = queue1.removeFirst()
            queue2.append(remove)
            queue1sum -= remove
            queue2sum += remove
        } else {
            let remove = queue2.removeFirst()
            queue1.append(remove)
            queue2sum -= remove
            queue1sum += remove
        }
        
        ans += 1
        
        // 탈출조건
        if queue1.isEmpty || queue2.isEmpty {
            return -1
        }
    }
    
    return ans
}

합계: 83.3 / 100.0

3️⃣ <3차 풀이>

func solution(_ queue1:[Int], _ queue2:[Int]) -> Int {
    var maxCnt = queue1.count + queue2.count
    var queue1 = queue1
    var queue2 = queue2
    var queue1sum = queue1.reduce(0, +) 
    var queue2sum = queue2.reduce(0, +)
    var ans = 0
    
    while queue1sum != queue2sum {
        if queue1sum >= queue2sum {
            let remove = queue1.removeFirst()
            queue2.append(remove)
            queue1sum -= remove
            queue2sum += remove
        } else {
            let remove = queue2.removeFirst()
            queue1.append(remove)
            queue2sum -= remove
            queue1sum += remove
        }
        
        ans += 1
        
        // 탈출조건
        if queue1.isEmpty || queue2.isEmpty || ans > maxCnt {
            return -1
        }
    }
    
    return ans
}

합계: 86.7 / 100.0

직접 큐(Queue) 자료구조를 이용하지 않고 단순히 배열을 큐로 사용하면 0번 원소를 지우는 과정에서 시간 초과가 발생할 수도 있다….

4️⃣ <4차 풀이 - 풀이방법 투포인터로 변경>

func solution(queue1:[Int], queue2:[Int]) -> Int {
    var maxCnt = queue1.count * 4
    var queue = queue1 + queue2
    var pointer = (0, queue1.count)
    var queue1sum = queue1.reduce(0, +)
    var queue2sum = queue2.reduce(0, +)
    var ans = 0
    
    while queue1sum != queue2sum {
        if queue1sum >= queue2sum {
            queue1sum -= queue[pointer.0]
            queue2sum += queue[pointer.0]
            pointer.0 += pointer.0 + 1 > queue.count - 1 ? 0 : 1
        } else {
            queue1sum += queue[pointer.1]
            queue2sum -= queue[pointer.1]
            pointer.1 += pointer.1 + 1 > queue.count - 1 ? 0 : 1
        }
        
        ans += 1
        
        // 탈출조건
        if ans > maxCnt {
            return -1
        }
    }
    
    return ans
}

💬 알게된 것

• queue를 구현하기 위해 단순 배열을 이용하여 dequeue를 할 때 removeFirst는 시간이 많이 걸린다.

  • 이유?
    • Swift는 Queue가 구현이 되어 있지 않아서, 직접 배열로 구현을 해야함.

• maxCnt가 4배인 이유

  • 이때, 전체 배열의 길이가 2n이므로, 한 포인터 당 최대 2n번의 이동이 필요합니다. 따라서, 총 4n만큼의 작업을 수행한 뒤에도 두 큐의 합을 같게 만들지 못했다면 그 이후에는 이미 탐색했던 구간을 다시 탐색하는 것이므로 의미가 없습니다. 이 경우에는 -1을 반환