[pro] 프로그래머스 level2 118667 두 큐 합 같게 만들기 (Java) - 큐

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/118667

프로그래머스

 

[풀이]

두 큐의 합을 같게 만들기 위해서는 한 쪽 큐의 합이 (두 큐의 합)/2 가 되면 된다.

고려해야 할 것은 queue1과 queue2 중 어느 큐의 숫자를 옮길 것인지 선택해야 하는데, 이는 한쪽 큐의 합에 따라 달렸다.

만약 queue1의 합이 (두 큐의 합)/2 보다 작으면 queue2의 숫자를 빼와서 넣어줘야 하고, 크다면 queue1의 숫자를 빼서 queue2에 넣어줘야 한다. 

 

(큐의 길이*3) 만큼 숫자를 이동시켜도 값이 같아지지 않는다면 -1을 반환한다. 

 

[코드]

 

import java.util.*;

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        int answer = 0;
        // 각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수
        Queue<Integer> q1 = new LinkedList<>();
        Queue<Integer> q2 = new LinkedList<>();
        
        long sum = 0;
        long q1_sum = 0;
        for(int i=0; i<queue1.length; i++){
            sum += queue1[i];
            sum += queue2[i];
            q1_sum += queue1[i];
            q1.add(queue1[i]);
            q2.add(queue2[i]);
        }
        
        long mid = sum/2;
        int cnt = queue1.length*3;
        
        while(q1_sum!=mid){
            if(cnt==0){
                return -1;
            }
            if(q1_sum > mid){
                int num = q1.poll();
                q1_sum -= num;
                q2.add(num);
                answer++;
            }
            else if(q1_sum < mid){
                int num = q2.poll();
                q1_sum += num;
                q1.add(num);
                answer++;
            }
            cnt--;
        }
        
        return answer;
    }
    
}