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

오랜만에 문제 풀이 블로깅인 것 같다.

이번엔 2022 KAKAO TECH INTERNSHIP > 두 큐 합 같게 만들기 문제를 풀어보았다.

문제를 읽어보면 알겠지만, 대놓고 Queue를 써보라고 유혹하고 있다.

하지만, 이 문제는 투 포인터로 해결이 가능했다.

종료 조건을 잘 체크해야지 무한루프에서 빠져나올 수 있고, java에서는 계산시에 산술 오버플로우가 생길 수 있어 long으로 풀어줘야 한다. (이거때문에 삽질함..)

---

풀이 방법은 queue1 과 queue2를 하나의 배열에서 생각하기로 했다.
IntStream.concat(Arrays.stream(queue1), Arrays.stream(queue2)).toArray() 를 사용해서 해당 Stream 메서드를 통해서 쉽게 두 배열을 하나의 배열로 합칠 수 있다.

이후 합친 배열에서 각 큐의 인덱스의 초기 위치를 설정한다.

종료 조건으로는 어느 한 큐 라도 비었을 때, 인덱스가 배열 범위를 넣었을 때, 두 인덱스가 만날때 이다.
전부 두 큐의 합을 같게 할 수 없는 상태이다.

내부 로직에는 각 큐의 합을 비교하면서 빼고 넣고 하는 작업 + 인덱스를 옮기는 작업을 하게된다.

사실 그렇기 어렵지는 않았지만, 삽질을 많이 했던 문제였다..

import java.util.*;
import java.util.stream.*;
/**
최종합/2 를 통해 target 값을 찾음.
한 큐 에서 target 값 만들기가 가능하다면 바로 return
종료 조건은? 어느 한 큐에서 empty 가 되었을때?
*/

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        int[] arr = IntStream.concat(Arrays.stream(queue1), Arrays.stream(queue2)).toArray();
        long q1Sum = 0;
        long q2Sum = 0;
        
        for (int i=0; i<queue1.length; i++) {
            q1Sum += queue1[i];
            q2Sum += queue2[i];
        }
        
        long target = (q1Sum + q2Sum) / 2;
        int result = -1;
        int count = 0;
        int q1Index = 0;
        int q2Index = queue1.length;
        while ((q1Sum != 0 && q2Sum != 0) && (q1Index < arr.length && q2Index < arr.length) && (q1Index != q2Index)) {
            if (q1Sum < q2Sum) {
                int temp = arr[q2Index];
                q2Sum -= temp;
                q1Sum += temp;
                q2Index++;
            } else if (q1Sum > q2Sum) {
                int temp = arr[q1Index];
                q1Sum -= temp;
                q2Sum += temp;
                q1Index++;
            } else if (q1Sum == q2Sum) {
                result = count;
                break;
            }
            
            count++;
        }
        
        return result;
    }
}