[JAVA] 프로그래머스 - 두 큐 합 같게 만들기 - 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가지 방법이 있습니다.

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 고려가 필요합니다.

---

문제풀이

문제에 나와있든 주어진 두큐의 전체 합/2 를 하면 두큐의 합이 되야하는 숫자가 나온다.

예를들어 총 20이라면 큐는 하나당 10, 10이라는 합을 갖어야한다는 소리다.

 

이는 잘 생각해보면 간단하게 풀수 있다. 먼저 총합/2(target)을 구하고, 현재 큐 하나의 합을 구한다.

그리고 투포인터의 특정값을 찾을때 처럼 1번큐의 합이 target보다 크다면 1번큐에서 poll하고 2번큐에 push한다.

1번큐의 합이 target보다 작다면 2번큐에서 poll하고 1번큐에 push한다.

이를 무한히 반복한다.

종료조건은 1번큐의 합이 target과 같아질때 && 작업횟수가 두큐의 크기보다 적당히 커졌을땐 같게 만들수 없다는 뜻이므로 종료한다.

 

사실 2번째 종료조건에서 필자는 "작업횟수 > (1번큐길이+2번큐길이)*2" 를 했지만

"작업횟수 > (1번큐길이+2번큐길이)+2" 도 문제에선 통과가 가능하다. 내생각엔 정확한 기준은 없으나, 중요한건 2개의 큐길이 합 만큼만 순회 시킨다면 반례가 존재하기 때문에 무조건 길이의 합보다 크게 잡아야 한다는 것이다.

 

---

코드

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

public class Solution {
	public static int solution(int[] q1, int[] q2) {
		int ans = 0;
		
		long total=0;//두큐의합
		long q1Sum=0;//1번큐의합
		Queue<Integer> qq1 = new LinkedList<Integer>();
		Queue<Integer> qq2 = new LinkedList<Integer>();
		for(int i=0; i<q1.length; i++) { 
			total += q1[i]+q2[i];
			q1Sum += q1[i];
			qq1.add(q1[i]);
			qq2.add(q2[i]);
		}
		if(total%2!=0) return -1;//만약 두큐의합이 홀수면 같게 못만듦.
		
		long target = total/2;
		while(true) {
			if(ans>(q1.length+q2.length)*2) return -1;//이땐 더 순회해도 못만듦
			if(q1Sum==target) break;
			else if(q1Sum>target) {
				q1Sum-=qq1.peek();
				qq2.add(qq1.poll());
			}else {
				q1Sum += qq2.peek();
				qq1.add(qq2.poll());
			}
			ans++;
		}
		
		return ans;
	}
}

---

마치며

최근데 백준 문제를 풀면서 좀 생각해봐야하는 문제가 많아서 그랬을까,, 프로그래머스 문제를 오랜만에 풀었는데 백준보다 쉽게 느껴진다. 아무튼 재밌는 문제다.