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

 

문제 설명

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의 원소 ≤ 109
주의: 언어에 따라 합 계산 과정 중 산술 오버플로우 발생 가능성이 있으므로 long type 고려가 필요합니다.

 

 

두개의 배열 in[]가 있을 때 이 배열은 queue처럼 선입 선출되는 구조라고 한다.

이때 배열 in[] queue1에서 pop()한 뒤 int[] queue2(상대 배열)에 insert하는 과정을 1회라고 카운트한다.

pop(), insert()하는 과정에서 int[] queue1, int[] queue2의 합이 같도록 하는 최소 카운트 횟수를 반환하는 것이 문제이다.

하지만 두 배열(큐)가 합이 같아지지 않을 경우 -1을 반환한다.

알고리즘

queue를 따로 만들지 않고 누적합을 이용해서 같을 때까지 queue2[idx++] 이런식으로 풀수 있나 고려해봤는데

한정적인 인덱스를 갖고있는 배열은 해당 방법으론 풀 수 없었다. 그렇게 누적합을 통해서 만들려면 새로운 배열이나 어차피 다른 구조를 가져와야할 것 같아서 쓸모 없다고 생각했다.

queue 자료형처럼 선입선출되는 것을 코드상 구현 해볼까? 싶었지만 그것 또한 쓸모 없는 것 같았다.

그래서 Queue 자료형을 가지고 와서 합이 같아질 동안 poll()(뽑고), add()(넣고)를 반복하는 방법밖에 떠오르지 않았다.

 

해결 방법

import java.util.*;
import java.util.stream.Collectors;

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        int answer = 0;
        long queue1Sum = Arrays.stream(queue1).sum();
        long queue2Sum = Arrays.stream(queue2).sum();
        int totalCount = queue1.length + queue2.length;
        if (queue1Sum == queue2Sum) {
            return 0;
        }
        
        if ((queue1Sum + queue2Sum) % 2 != 0) {
            return -1;
        }
        
        Queue<Integer> q1 = new LinkedList<>(Arrays.stream(queue1).boxed().
                                             collect(Collectors.toList()));
        Queue<Integer> q2 = new LinkedList<>(Arrays.stream(queue2).boxed().
                                             collect(Collectors.toList()));
        
    
        while(queue1Sum != queue2Sum) {
            if (queue1Sum < queue2Sum) {
                answer++;
                int tmpQ2 = q2.poll();
                queue2Sum -= tmpQ2;
                queue1Sum += tmpQ2;
                q1.add(tmpQ2);
            } else if (queue1Sum > queue2Sum) {
                answer++;
                int tmpQ1 = q1.poll();
                queue1Sum -= tmpQ1;
                queue2Sum += tmpQ1;
                q2.add(tmpQ1);
            }
            
            if (answer > totalCount * 2) {
                return -1;
            }
        }
        return answer;
    }
}

 

같을 경우는 주지 않겠지만 빠른 도출 방법을 위해 넣었고, 두 큐의 합이 홀수일경우 같을 수 없기 때문에 if문으로 앞에 뒀다.

또한 아무리 빼고 넣는 것을 반복해도 같아 지지 않을 경우는 answer(카운트 횟수)가 두 큐의 배열 길이의 2배 이상이 될것이다. 이때 if 문으로 -1을 반환하도록 해서 무한루프에 빠지지 않도록 했다.

 

더 좋은 해결 방법

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        int[] totalQueue = new int[queue1.length + queue2.length];
        long queue1Sum = 0;
        long queue2Sum = 0;

        for(int i = 0; i < queue1.length; i++) {
            int val = queue1[i];
            totalQueue[i] = val;
            queue1Sum += val;    
        }

        for(int i = queue1.length; i < queue1.length + queue2.length; i++) {
            int val = queue2[i - queue1.length];
            totalQueue[i] = val;
            queue2Sum += val;    
        }

        if((queue1Sum + queue2Sum) % 2 == 1) return -1;

        int count = 0;
        int left = 0;
        int right = queue1.length;
        long half = (queue1Sum + queue2Sum) / 2;
        while(left < right && right < totalQueue.length) {
            if(queue1Sum == half) {
                return count;
            } else if(queue1Sum > half) {
                queue1Sum -= totalQueue[left++];
            } else {
                queue1Sum += totalQueue[right++];
            }
            count++;
        }
        return -1;
    }
}

 

이건 아예 queue1, queue2 길이를 합한 길이대로 배열을 만든 뒤

누적합처럼 빼고 더하면서 같아질때 count값을 반환하는 코드다.

 

나는 항상 두개를 같은 자료구조에 담을 생각을 못하고 따로따로 둬야한다는 생각이 조금 더 지배적인것 같아서 해당 구현방법을 생각 못했는데 내가 머릿속으로 생각한 구현방법이 위와 같은 코드였다.