[2022 KAKAO TECH INTERNSHIP] 두 큐 합 같게 만들기

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/118667

[이 문제는 프로그래머스에서 푼 문제입니다.]
이 문제는 큐를 이용하여 문제 조건을 하나하나 구현하면 풀 수 있습니다. 전체적인 로직은 다음과 같습니다.

1. 각 큐의 합을 계산한다.
2. 이 때 최댓값이 나머지의 합보다 크다면 -1을 리턴한다.
3. 각 큐의 합이 같을때까지 반복문을 돌린다.
4. 합이 큰 쪽에서 pop하고 작은 쪽에 해당 값을 insert한다 (그리디)
5. 큐에 담긴 모든 원소들을 다른 큐로 옮기고 다시 원래대로 돌아오는데 걸리는 횟수는 초기 큐의 4배이기 때문에 해당값보다 크다면 한 바퀴 돈 것이므로 -1 리턴

다음은 코드입니다.

import java.util.*;

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        // 각 큐의 합 계산
        int max = 0;
        
        Queue<Integer> q1 = new LinkedList<>();
        Queue<Integer> q2 = new LinkedList<>();
        
        long sum1 = 0;
        long sum2 = 0;
        
        for(int i=0;i<queue1.length;i++){
            q1.add(queue1[i]);
            sum1 += queue1[i];
            if(max < queue1[i]) max = queue1[i];
        }
        
        for(int i=0;i<queue2.length;i++){
            q2.add(queue2[i]);
            sum2 += queue2[i];
            if(max < queue2[i]) max = queue2[i];
        }
        
        // 이 때 최댓값이 나머지의 합보다 크다면 -1 리턴
        if((sum1+sum2-max) < max) return -1;
        
        // 값이 같을때까지 실행
        int answer = 0;
        while(true){
            // 큐에 담긴 모든 원소들을 다른 큐로 옮기고 다시 원래대로 돌아오는 횟수 = 초기 큐의 4배
            // 따라서 초기 큐의 길이의 4배보다 크다면 한 바퀴 돈 것이므로 -1 리턴
            if(answer > queue1.length * 4) return -1;
            
            // 만약 sum1 < sum2라면 q2를 pop하고 q1에 해당값을 insert
            if(sum1 < sum2){
                int val = q2.poll();
                q1.add(val);
                sum1 += val;
                sum2 -= val;
            }
            // 만약 sum2 < sum1라면 q1를 pop하고 q2에 해당값을 insert
            else if(sum1 > sum2){
                int val = q1.poll();
                q2.add(val);
                sum1 -= val;
                sum2 += val;
            }
            // 두 값이 같다면 break
            else break;
            
            answer++;
        }
        
        return answer;
    }
}