[TIL] 프로그래머스) 두 큐 합 같게 만들기 풀이 (Java)

 

학습 키워드: Java, Queue, Array

 

118667 - 두 큐 합 같게 만들기

프로그래머스

 

1) 문제 설명 요약 (원문은 링크 참고):

 요약: 길이가 같은 배열 queue1과 queue2를 큐라고 가정하고, 최소한의 횟수로 pop() 및 insert() 하여 각 큐의 합이 동일한 상태가 되는 경우의 작업 카운트를 구하는 문제입니다. pop() 과 insert()를 한 번씩 실행한 것을 한 번의 작업 카운트로 취급합니다.

 조건: 1 <= queue1의 길이 = queue2의 길이 <= 300,000, 1 <= queue1의 원소, queue2의 원소 <= 10^(9)

 

 

2) 풀이 과정:

 2022 KAKAO TECH INTERNSHIP 문제로, 며칠 전에 풀 때는 도저히 안풀리던 문제가 오늘 갑자기 코드 초기화를 한 번 하고 풀어보니 잘 풀렸다. 문제에서 이미 Queue를 array의 형태로 넘겨주는데, 이 배열을 Queue로 바꾸지 않고 배열의 index를 가리키는 포인터(C 포인터 아님)를 생성 및 조작하여 풀어내는 것이 핵심이다.

 

 일단 처음 주어지는 두 배열의 길이가 같기 때문에 for loop 한 번으로 각 배열의 현재 합을 구해준다. 이후 각각의 배열에 해당하는 index 포인터 p1과 p2를 만들어 초기 값을 0으로 설정해준다. 두 배열의 sum 값이 일치하는지 확인하는 while 루프를 돌면서 '작업'을 수행하면 된다.

 

 그 전에 우선 '작업'을 수행하는 기준을 알아야한다. 두 큐의 합을 같게 만들기 위해서는 큐의 합을 비교했을 때 더 큰 값을 가지고 있는 큐에서 값을 빼주고 그 값을 다른 값에 넣어주면 된다. 그런데 주어진 큐가 실제론 array라서 실제로 값이 pop 또는 insert 되지는 않는다. 따라서 이 '작업'은 배열 길이 이상으로 호출될 수 없다. 그렇다면 어떻게 해야할까?

 

 바로 배열의 포인터 위치를 바꿔주는 작업이 필요하다. 각 큐에서 pop되어 다른 큐로 insert된 항목은 맨 뒤에 이어붙게된다. 이 말인 즉, queue1의 모든 값이 queue2로 이동되는 경우 queue1의 pop이 다음에 받아야하는 값은 queue2에서 pop되고 queue1에 insert되는 queue2의 맨 앞 값이 되는 것이다. 따라서 queue1 배열의 포인터가 index의 bound를 초과하는 시점에서 queue1의 index 포인터는 queue2의 0번 index를 가리키면 되는 것이다. 이를 코드로 구현하면 아래와 같다.

 

 

3) 코드:

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        int count = 0;
        int p1 = 0;
        int p2 = 0;
        long sum1 = 0;
        long sum2 = 0;
        for (int i = 0; i < queue1.length; i++) {
            sum1 += queue1[i];
            sum2 += queue2[i];
        }
        
        boolean sw1 = false;
        boolean sw2 = false;
        while (sum1 != sum2) {
            if (sum1 > sum2) {
                if (!sw1) {
                    sum1 -= queue1[p1];
                    sum2 += queue1[p1++];
                }
                else {
                    sum1 -= queue2[p1];
                    sum2 += queue2[p1++];
                }
                if (p1 >= queue1.length) {
                    if (sw1) break;
                    p1 = 0;
                    sw1 = true;
                }
                count++;
            }
            else if (sum1 < sum2) {
                if (!sw2) {
                    sum2 -= queue2[p2];
                    sum1 += queue2[p2++];
                }
                else {
                    sum2 -= queue1[p2];
                    sum1 += queue1[p2++];
                }
                if (p2 >= queue1.length) {
                    if (sw2) break;
                    p2 = 0;
                    sw2 = true;
                }
                count++;
            }
        }
        
        if (sum1 == sum2) return count;
        return -1;
        
    }
}

 생각나는대로 빠르게 구현해본 코드인데, 리팩토링이 가능한지는 좀 더 고민을 해봐야 할 것 같다.