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

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

문제 설명

길이가 같은 두 개의 큐가 주어집니다. 하나의 큐를 골라 원소를 추출(pop)하고, 추출된 원소를 다른 큐에 집어넣는(insert) 작업을 통해 각 큐의 원소 합이 같도록 만들려고 합니다. 이때 필요한 작업의 최소 횟수를 구하고자 합니다. 한 번의 pop과 한 번의 insert를 합쳐서 작업을 1회 수행한 것으로 간주합니다.

큐는 먼저 집어넣은 원소가 먼저 나오는 구조입니다. 이 문제에서는 큐를 배열로 표현하며, 원소가 배열 앞쪽에 있을수록 먼저 집어넣은 원소임을 의미합니다. 즉, pop을 하면 배열의 첫 번째 원소가 추출되며, insert를 하면 배열의 끝에 원소가 추가됩니다. 예를 들어 큐 [1, 2, 3, 4]가 주어졌을 때, pop을 하면 맨 앞에 있는 원소 1이 추출되어 [2, 3, 4]가 되며, 이어서 5를 insert하면 [2, 3, 4, 5]가 됩니다.

다음은 두 큐를 나타내는 예시입니다.

queue1 = [3, 2, 7, 2]
queue2 = [4, 6, 5, 1]
두 큐에 담긴 모든 원소의 합은 30입니다. 따라서, 각 큐의 합을 15로 만들어야 합니다. 예를 들어, 다음과 같이 2가지 방법이 있습니다.

queue2의 4, 6, 5를 순서대로 추출하여 queue1에 추가한 뒤, queue1의 3, 2, 7, 2를 순서대로 추출하여 queue2에 추가합니다. 그 결과 queue1은 [4, 6, 5], queue2는 [1, 3, 2, 7, 2]가 되며, 각 큐의 원소 합은 15로 같습니다. 이 방법은 작업을 7번 수행합니다.
queue1에서 3을 추출하여 queue2에 추가합니다. 그리고 queue2에서 4를 추출하여 queue1에 추가합니다. 그 결과 queue1은 [2, 7, 2, 4], queue2는 [6, 5, 1, 3]가 되며, 각 큐의 원소 합은 15로 같습니다. 이 방법은 작업을 2번만 수행하며, 이보다 적은 횟수로 목표를 달성할 수 없습니다.
따라서 각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수는 2입니다.

길이가 같은 두 개의 큐를 나타내는 정수 배열 queue1, queue2가 매개변수로 주어집니다. 각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수를 return 하도록 solution 함수를 완성해주세요. 단, 어떤 방법으로도 각 큐의 원소 합을 같게 만들 수 없는 경우, -1을 return 해주세요.

제한 사항

• 1 ≤ queue1의 길이 = queue2의 길이 ≤ 300,000
• 1 ≤ queue1의 원소, queue2의 원소 ≤ 10^9
• 주의: 언어에 따라 합 계산 과정 중 산술 오버플로우 발생 가능성이 있으므로 long type 고려가 필요합니다.

접근

문제 접근 방식이 떠오르지 않아 카카오 테크 블로그 해설을 기반을 구현했습니다.

카카오 2022 테크 여름인턴십 코딩테스트 해설
https://tech.kakao.com/2022/07/13/2022-coding-test-summer-internship/

해당 문제는 탐욕적 알고리즘으로 queue1, queue2 두 큐의 합을 비교하여 queue1 < queue2인 경우 queue1의 원소를 queue2에 더해주며, 반대로 queue1 > queue2인 경우 queue2의 원소를 queue1에 더해주어 서로 합이 같아질 때까지 반복해 주면 됩니다.

하지만 배열을 직접 자르고 다른 배열에 이어붙이는 과정이 시간 초과를 발생할 수 있어 큐 자료구조의 특성을 이용해 투 포인터 방식으로 문제를 해결할 수 있습니다.

큐에서 원소를 반환(pop) 할 때는 맨 앞쪽 원소를 반환하고, 원소를 삽입(insert) 할 때는 마지막 자리에 위치합니다. 이 점을 이용해 반환할 배열의 맨 왼쪽 포인터를 한 칸 더 이동해 값을 포함시키지 않고 집어넣을 배열의 오른쪽 포인터를 한 칸 더 이동해 값을 포함시킵니다.

queue1 = [1, 2, 1, 2], queue2 = [1, 10, 1, 2]를 예시로 모든 원소의 합은 20으로 각 큐의 합을 10으로 만들어야 합니다. 편의상 queue1 배열은 L, queue2의 배열은 R로 표현합니다.

step1. L의 합은 6, R의 합은 14로 R의 합이 더 크기 때문에 L의 오른쪽 포인터를 이동해 포인터가 가리키고 있는 1을 L의 합에 더해주고, R의 왼쪽 포인터를 이동해 포인터가 가리키고 있는 1을 R의 합에 빼줍니다.

step2. L의 합은 7, R의 합은 13으로 여전히 R의 합이 더 크기 때문에 L의 오른쪽 포인터를 이동해 포인터가 가리키고 있는 10을 L의 합에 더해주고, R의 왼쪽 포인터를 이동해 포인터가 가리키고 있는 10을 queue2의 합에 빼줍니다.

step3. L의 합은 17, R의 합은 3으로 L의 합이 더 커졌기 때문에 반대로 R의 오른쪽 포인터를 이동해 포인터가 가리키고 있는 1을 R의 합에 더해주고, L의 왼쪽 포인터를 이동해 포인터가 가리키고 있는 1을 L의 합에 빼줍니다.단, R의 오른쪽 포인터 이동 시 합쳐진 배열의 길이를 초과하기 때문에 원점으로 이동합니다.

두 배열의 합을 비교하고 값이 작은 배열의 포인터를 이동해 배열의 합을 더해 주는 작업을 두 배열의 합이 같아질 때까지 반복합니다. 단 각 배열의 모든 포인터를 이동할 때까지 두 배열의 합이 같아지지 않는다면 작업을 중단해 줍니다. 합쳐진 배열의 길이의 두 배만큼 횟수만큼 반복했다면 다시 배열을 원점으로 되돌린 것과 마찬가지이므로 4n만큼만 반복해 줍니다.

풀이

import java.util.*;

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        int answer = 0;
        int n = queue1.length;
        
        // 하나의 배열로 합치기
        long[] merged = new long[n * 2];
        
        for (int i = 0; i < n; i++) {
            merged[i] = queue1[i];
        }

        for (int i = 0; i < n; i++) {
            merged[n + i] = queue2[i];
        }
       
        // 각 큐의 합 계산 
        long q1Sum = Arrays.stream(queue1).sum();
        long q2Sum = Arrays.stream(queue2).sum();
        
        // 모든 원소의 합이 홀수인 경우 종료  
        if ((q1Sum+ q2Sum) % 2 != 0) {
            return -1;
        }
        
        long target = (q1Sum+ q2Sum) / 2;
        
        // queue1의 왼쪽, 오른쪽 포인터
        int l1 = 0;
        int r1 = n - 1;
                
        // queue2의 왼쪽, 오른쪽 포인터
        int l2 = n;
        int r2 = n * 2 - 1;
        
        // 배열의 모든 구간을 탐색한 경우 종료 
        // 배열의 길이는 2n으로 한 번의 연산은 두 포인터를 이동하므로 두 배 
        while (answer < 4 * n) {
        	// queue1의 합이 목표 값보다 작은 경우 
            if (q1Sum < target) {
                // queue1 오른쪽 포인터를 이동하여 값을 증가
                // queue2 왼쪽 포인터 이동하여 값을 감소
                r1 = (r1 + 1) % merged.length;          
                l2 = (l2 + 1) % merged.length; 

				q1Sum += merged[r1];
				q2Sum -= merged[r1];

				answer += 1;
            }
			// queue2의 합이 목표 값보다 작은 경우 
            if (q2Sum < target) {
                // queue2 오른쪽 포인터를 이동하여 값을 증가
                // queue1 왼쪽 포인터 이동하여 값을 감소
                r2 = (r2 + 1) % merged.length; 
                l1 = (l1 + 1) % merged.length; 
                
                q2Sum += merged[r2];
                q1Sum -= merged[r2];
                
                answer += 1;
            }

			// 두 큐의 합이 목표 값과 같으면 종료
            if (q1Sum == target && q2Sum == target) {
                break;
            }
        }

        return q1Sum == q2Sum ? answer : -1;
    }
}

결과