프로그래머스 | 두 큐 합 같게 만들기 (Java)

🔒 문제

프로그래머스 Lv.2 2022 KAKAO TECH INTERNSHIP

🔑 해결

길이가 같은 두 개의 큐를 나타내는 정수 배열이 매개변수로 주어질 때, 각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수를 return하는 solution함수를 작성하는 문제이다.

1. 모든 원소의 합(all), 각 큐의 합(sum1, sum2)를 구한 후에 linkedlist에 각 배열의 원소를 순서대로 add한다.
2. 각 큐의 원소의 합이 같기 위해서는 all(모든 원소의 합)이 짝수여야 한다. all % 2가 0이 아니라면 -1를 return한다. 짝수가 아니라면 target(만들어야 하는 각 큐의 합) = all / 2
3. 반복문을 통해 큐의 합이 큰 쪽에서 원소를 pop하여 작은 쪽에 add한다.
4. pop하고 add하면서 원소를 이동하는 작업을 한 후 각 큐의 합(sum1, sum2)가 target과 같다면 반복문을 끝낸다.
5. 각 큐의 원소 합을 같게 만들 수 없는 경우 (큐가 비어 sum이 0이거나, 작업 횟수가 큐 길이의 2배 이상) -1을 return

🔓 코드

import java.util.LinkedList;
class Solution {
    public int solution(int[] queue1, int[] queue2) {
        int answer = -2;
        
        long all = 0, sum1 = 0, sum2 = 0;
        
        LinkedList<Integer> list1 = new LinkedList<Integer>();
        LinkedList<Integer> list2 = new LinkedList<Integer>();
        for (int i = 0; i < queue1.length; i++) {
			all += queue1[i];
			sum1 += queue1[i];
			list1.add(queue1[i]);
			
			all += queue2[i];
			sum2 += queue2[i];
			list2.add(queue2[i]);
		}
        
        if (all % 2 != 0)
            return -1;
        long target = all / 2;
        int count = 0;
       
        while (sum1 != target || sum2 != target) {
        	if (sum1 < sum2 && !list2.isEmpty()) {
        		int num = list2.pop();
        		list1.add(num);
        		sum1 += num;
        		sum2 -= num;
        	} else if (sum1 > sum2 && !list1.isEmpty()) {
        		int num = list1.pop();
        		list2.add(num);
        		sum2 += num;
        		sum1 -= num;
        	}
        	count++;
  	
        	if (sum1 == target || sum2 == target)
        		break;
        	if (sum1 == 0 || sum2 == 0 || count > 600000)
        		return -1;
        }
        answer = count;
        
        return answer;
    }
}