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

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

연습이 덜 된 상태로 처음 응시한 카카오 코테에서 막혔던 문제인데, 프로그래머스 코딩테스트 연습에 올라와서 다시 풀어보았다.

두 큐가 존재하고, 두 큐의 모든 원소의 합이 동일하게 만드는 최소 이동 횟수를 반환하는 문제이다.

두 큐의 길이가 최대 300,000이고 각 원소는 최대 1억이다.

예시 테스트케이스는 아래와 같다.

queue1 = {3, 2, 7, 2}, queue2 = {4, 6, 5, 1}, answer = 2
queue1 = {1, 2, 1, 2}, queue2 = {1, 10, 1, 2}, answer = 7

큐의 길이가 최대 300,000이므로 최초에 각 큐의 원소의 합을 구해 놓고, 포인터 두 개를 이용해 부분합을 사용해야겠다 생각하였다.

첫 번째 테스트케이스를 예시로 과정을 구상해보았다.

1. queue1의 합 = 14이고 queue2의 합 = 16이다

2. 두 큐를 합친 연결 큐를 만든다.
   q1 = {3, 2, 7, 2, 4, 6, 5, 1}
   q2 = {4, 6, 5, 1, 3, 2, 7, 2}

+) 연결 큐를 만드는 이유는, 반대 큐에서 원소가 들어왔을 때를 위해서이다.
q1 = {3, 2, 7, 2, 4, 6, 5, 1} 이지만 최초 size는 4로 둔다.
만약 q2에서 4라는 원소가 q1로 들어온다면 q1의 size를 5로 간주해 원소 4까지 포함하도록 만듦.

3. 포인터 ptr1과 ptr2를 준비한다 (인덱스).

4. sum1과 sum2를 반복적으로 비교하며 sum1이 크다면 q2[ptr2]의 값을 sum1에서 빼고 sum2엔 더한다 (q2의 앞 원소를 q1에 넣는 의미)

5. sum1과 sum2가 같거나, ptr1이 q1의 마지막에 오거나, ptr1이 queue1의 크기 + ptr2와 같으면 (ptr2도 동일) 반복문에서 탈출하도록 한다.

+) queue1의 크기 + ptr2의 값이 위에서 말한 현재 큐의 size를 의미한다.
{3, 2, 7, 2}로 4개였는데 ptr2가 증가함으로써 (q2의 원소가 1개 들어옴) {3, 2, 7, 2, 4}가 된 것처럼 간주한 것이다.

class Solution {
    fun solution(queue1: IntArray, queue2: IntArray): Int {
        var sum1 = 0L
        var sum2 = 0L

        queue1.forEach { sum1 += it }
        queue2.forEach { sum2 += it }

        val q1 = IntArray(queue1.size + queue2.size){
            if(it < queue1.size) queue1[it]
            else queue2[it - queue1.size]
        }

        val q2 = IntArray(queue1.size + queue2.size){
            if(it < queue2.size) queue2[it]
            else queue1[it - queue2.size]
        }

        var ptr1 = 0
        var ptr2 = 0

        var found = false
        while(true){
            if(ptr1 == queue1.size + ptr2 || ptr1 == q1.size) break
            if(ptr2 == queue2.size + ptr1 || ptr2 == q2.size) break

            when{
                sum1 > sum2 -> {
                    sum1 -= q1[ptr1]
                    sum2 += q1[ptr1++]
                }
                sum1 < sum2 -> {
                    sum2 -= q2[ptr2]
                    sum1 += q2[ptr2++]
                }
                else -> {
                    found = true
                    break
                }
            }
        }

        return if(!found) -1 else ptr1 + ptr2
    }
}