[프로그래머스] 두 큐 합 같게 만들기 - JAVA

카카오 2022 테크 인턴쉽 코딩테스트 2번 문제로 공식 해설을 기반으로 문제를 풀었습니다.

2022 테크 여름인턴십 코딩테스트 해설

문제는 프로그래머스에서 확인하실 수 있습니다.

프로그래머스

풀이

두 가지 풀이법이 있습니다. Queue 자료형을 사용하는 것과 투포인터 알고리즘을 사용하는 것입니다. 우선 공통된 아이디어에 대해 설명하겠습니다. 주어진 두 배열은 큐의 특성을 가지며 pop, insert를 통해 FIFO가 이루어집니다. 이를 그림으로 그리면 다음과 같습니다.

원형으로 연결된 두 큐

이런식으로 두 개의 큐를 연결할 수 있습니다. 그리고 각 큐의 합을 동일하게 만드려면 pop과 insert하는 과정이 필요합니다. 이때 큐의 원소의 합이 큰 쪽에서 작은 쪽으로 원소를 insert 해주면 됩니다. 이 방법이 유효한 이유는 pop을 하여 insert하는 방향이 정해져 있기 때문이다. 두 큐의 어느 순간의 합은 같거나 차이가 날 것이다. 이 때 합이 다른 경우, 두 큐의 차를 줄이기 위해서는 합이 큰 쪽의 큐의 원소를 작은 쪽으로 insert하는 방법 밖에 없다. 하지만 pop을 할 원소는 정해져 있기 때문에 매 순간 두 큐의 합을 비교하여 큰 쪽에서 작은 쪽으로 원소를 이동시키면 된다.

투 포인터로 이 상황을 표현해보자.

투 포인터로 배열된 두 배열

P1, P2를 기준으로 Sum1, Sum2가 나누어져 있다. 만약 Sum1 < Sum2라면 P1을 Sum2 쪽으로 이동하여 Sum1의 크기를 늘리면 된다.

그렇다면 두 큐의 합을 같게 하기 위해 pop, insert를 하거나 포인터를 움직이면 된다는 것을 알았다. 하지만 문제가 있다. Sum1과 Sum2의 값이 같아지는 경우가 있는 경우 중간에 정답을 리턴하겠지만 같아지지 않을 경우 포인터는 계속해서 회전할 것이다.

간단한 예시로 [1,1,1], [1, 1] 의 경우를 생각해보자. 왼쪽 큐의 값이 크므로 오른쪽으로 값을 이동시키면 다시 오른쪽 큐의 값이 커진다. 이 상황은 무한히 반복되며 어느 순간 이 상황이 무한히 반복될 것을 확인해 줘야 한다. 

큐를 사용한 경우 원래 큐의 사이즈를 저장해 두고 pop을 할 때 마다 사이즈를 1씩 빼주었다. 만약 양 쪽 큐의 pop 횟수가 원래 큐의 사이즈와 같아지면, 두 큐의 위치가 바뀌어도 합이 같아지지 않는 것이므로 그 때 -1을 리턴해주었다.

투 포인터를 사용한 경우에는 양 포인터의 위치가 서로의 최초 포인터의 위치를 지나면 -1을 리턴하게 하였다.

코드

import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    public int solution(int[] queue1, int[] queue2) {
        int answer = 0;

        Queue<Integer> q1 = new LinkedList<>();
        Queue<Integer> q2 = new LinkedList<>();
        long sum1 = 0;
        long sum2 = 0;

        for (int i : queue1) {
            q1.offer(i);
            sum1 += i;
        }

        for (int i : queue2) {
            q2.offer(i);
            sum2 += i;
        }

        int size1 = q1.size();
        int size2 = q2.size();

        while (!q1.isEmpty() && !q2.isEmpty()) {
            if (sum1 == sum2) return answer;

            if (sum1 > sum2) {
                size1--;
                int popped = q1.poll();
                q2.offer(popped);
                sum1 -= popped;
                sum2 += popped;
            } else {
                size2--;
                int popped = q2.poll();
                q1.offer(popped);
                sum2 -= popped;
                sum1 += popped;
            }

            if (size1 <= 0 && size2 <= 0) return -1;
            answer++;
        }

        return -1;
    }
}