[Java][프로그래머스] 118667번, 두 큐 합 같게 만들기

 

프로그래머스

 

118667, 두 큐 합 같게 만들기

📌 난이도 : LEVEL 2

 

📚 프로세스

요구사항

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

 

제한사항

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

 

문제풀이

맨 처음 구간합과 투포인터를 떠올렸다. 첫번째 큐와 두번째 큐의 합을 가지고 있다가 왼쪽의 합이 더 크면 poll한 값을 오른쪽으로 보내주는 알고리즘 구현을 목표로 했다. 우선 q1, 과 q2 를 넣을 Queue 를 생성하고, 각각의 큐의 합을 가지고 있기 보다는 두 큐의 합의 절반을 target 값으로 지정하고 첫번째 큐의 합의 값만 계산하여 들고간다.

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]);
}

 

여기서 두 큐의 합이 짝수가 아닌 경우 각각의 큐의 합이 같아질 수 없으니 -1 을 리턴한다. (두 큐의 합이 29일 경우 최적의 결과가 14, 15 이다. 즉, 두 큐의 합이 같아질 경우가 없다.) 이렇게 값을 설정한 후 투포인터 알고리즘을 사용한다.

첫번째 큐의 합과 total (두 큐의 합의 절반) 이 같아질 때까지 아래의 과정을 반복한다.

 

1. 첫번째 큐의 합이 타겟보다 클 경우, 첫번째 큐에서 수를 뽑아 그 값을 합에서 차감해주고 두번째 큐에 넣어준다.

2. 첫번째 큐의 합이 타겟보다 작을 경우, 두번째 큐에서 수를 뽑아 그 값을 합에서 차감해주고 첫번째 큐에 넣어준다.

//만약 두큐의합이 홀수면 같게 못만듦.
if(total%2!=0) 
    return -1;

long target = total/2;

while(q1Sum != target) {
    if(q1Sum > target) {
        q1Sum-=qq1.peek();
        qq2.add(qq1.poll());
    } else {
        q1Sum += qq2.peek();
        qq1.add(qq2.poll());
    }

    ans++;
}

 

여기서 주의할 사항은 반복 횟수에 대한 제약이다. 모든 큐의 합이 순회를 마쳤는데도 while 문이 끝나지 않는다면 Runtime 에러가 발생할 확률이 크다. 즉, 합쳐진 배열의 길이의 두 배만큼 횟수만큼 반복했다면 다시 배열을 원점으로 되돌린 것과 마찬가지이므로 4n만큼만 반복해 주고 작업을 중단해 주어야 한다. 

// 두 배열의 크기 * 2 만큼 작업을 진행한 경우, 모든 원소가 원점으로 돌아온 경우
// 작업 중단
if(ans > (q1.length+q2.length)*2) {
    return -1;
}

 

 

✅ 전체 코드

위의 과정을 통해 작성한 전체 코드는 아래와 같다.

import java.util.*;

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(q1Sum != target) {
			if(ans > (q1.length+q2.length)*2) {
            	return -1;
            }

			if(q1Sum > target) {
				q1Sum-=qq1.peek();
				qq2.add(qq1.poll());
			} else {
				q1Sum += qq2.peek();
				qq1.add(qq2.poll());
			}
            
			ans++;
		}
		
		return ans;
	}
}