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

 

프로그래머스

문제 설명

 

길이가 같은 두 개의 큐가 주어집니다. 하나의 큐를 골라 원소를 추출(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가지 방법이 있습니다.

1. queue2의 4, 6, 5를 순서대로 추출하여 queue1에 추가한 뒤, queue1의 3, 2, 7, 2를 순서대로 추출하여 queue2에 추가합니다. 그 결과 queue1은 [4, 6, 5], queue2는 [1, 3, 2, 7, 2]가 되며, 각 큐의 원소 합은 15로 같습니다. 이 방법은 작업을 7번 수행합니다.
2. 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 고려가 필요합니다.

 

입출력 예

queue1                                                                         queue2                                                                            result

[3, 2, 7, 2]	[4, 6, 5, 1]	2
[1, 2, 1, 2]	[1, 10, 1, 2]	7
[1, 1]	[1, 5]	-1

 

---

이문제에서 생각해야 했던 점은 탈출조건이다 최악의 케이스를 생각해 보자

queue1에서 queue2로 모든 값을 보내고 queue2에서 하나만을 제외하고 모두 queue1으로 내보내는 케이스이다

때문에 queue1의 길이의 3배(queue1, queue2의 길이가 같으므로)가 최악의 수라고 보면 된다

 

그리고 queue의 길이가 300,000이기 때문에  O(N²)으로 풀지 않고 O(nlogn)이나 O(n)으로 풀어야 한다

즉 완전탐색을 하면 안 된다는 뜻

---

import java.util.ArrayDeque;
import java.util.Queue;

public class PRO_CT_19 {
    public static int solution(int[] queue1, int[] queue2) {
        long sum1=0;
        long sum2=0;
        int count = 0;
        int max = queue1.length*3; //최악의 수

        ArrayDeque<Integer> deque1 = new ArrayDeque<>();
        ArrayDeque<Integer> deque2 = new ArrayDeque<>();

        for(int i=0;i<queue1.length;i++){
            sum1+=queue1[i];
            sum2+=queue2[i];
        }

        long result=(sum1+sum2);
        if(result%2!=0) return -1; //두큐의 합이 홀수면 두큐의 합이 같아질 수 없음
        if(sum1==sum2) return 0; //처음부터 같으면 바로 return

        for(int i=0;i<queue1.length;i++){
            deque1.addLast(queue1[i]);
            deque2.addLast(queue2[i]);
        }
        long midResult= result/2;
        
        while(count<=max){
            if(sum1>midResult){
                sum1-=deque1.peekFirst();
                sum2+=deque1.peekFirst();
                deque2.addLast(deque1.pollFirst());
            }else{
                sum1+=deque2.peekFirst();
                sum2-=deque2.peekFirst();
                deque1.addLast(deque2.pollFirst());
            }
            count++;
            if(sum1==(result/2)) return count;
        }

        return -1;
    }
    public static void main(String[] args) {
        int[] queue1 = {1,2,1,2};
        int[] queue2 = {1,10,1,2};
        System.out.println(solution(queue1,queue2));

    }
}

처음에 상식적으로 생각해야 할 점은 두 큐의 합이 홀수라면 두큐의 합을 같게 할 수 없기 때문에 바로 -1을 리턴해줘야 한다는 점

그리고 처음부터 두 큐의 합이 같으면 바로 0을 리턴해주고 이 두경우가 아닌 경우만 다음 연산을 해줘야 한다.

두 경우가 아니라면 count를 최악의 수만큼 while문을 돌린 후 큐의 합이 큰 쪽에서 값을 pop 해 작은 쪽으로 push 해주었다

통과!