[java] 프로그래머스 두 큐 합 같게 만들기

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

프로그래머스

 

처음코드

import java.util.*;
class Solution {
    public int solution(int[] queue1, int[] queue2) {
        int answer = -2;
        
        Queue<Integer> q1 = new LinkedList<>();
        Queue<Integer> q2 = new LinkedList<>();
        
        int sum1=0;
        int sum2=0;
        
        for(int i : queue1){
            q1.add(i);
            sum1 += i;
        }
        for(int i : queue2){
            q2.add(i);
            sum2 += i;
        }
        
        int fsum = (sum1+sum2)/2; 
        
        int cnt=0;
        while(!q1.isEmpty()){
            if(cnt>queue1.length+queue2.length){
                return -1;
            }
            if(sum1==sum2) break;
            if(sum1>fsum){
                int a = q1.poll();
                q2.add(a);
                cnt++;
                sum1 -= a;
                sum2 += a;
            }
            if(sum2>fsum){
                 int a = q2.poll();
                q1.add(a);
                cnt++;
                sum2 -= a;
                sum1 += a;
            }
        }
        
        
        return cnt;
    }
}

무엇이 문제인가?

long 으로 바꾸고

어떤 방법으로도 각 큐의 원소 합을 같게 만들 수 없는 경우를 생각해서

cnt는 q1과 q2의 합의 2배로 해야한다.

import java.util.*;
class Solution {
    public int solution(int[] queue1, int[] queue2) {
        int answer = -2;
        
        Queue<Integer> q1 = new LinkedList<>();
        Queue<Integer> q2 = new LinkedList<>();
        
        long sum1=0;
        long sum2=0;
        
        for(int i : queue1){
            q1.add(i);
            sum1 +=  (long)i;
        }
        for(int i : queue2){
            q2.add(i);
            sum2 +=  (long)i;
        }
        
        int cnt=0;
        while(sum1!=sum2){
            if(cnt>(queue1.length+queue2.length)*2){
                return -1;
            }
            if(sum1>sum2){
                int a = q1.poll();
                q2.add(a);
                cnt++;
                sum1 -= (long)a;
                sum2 +=  (long)a;
            }
            else if(sum2>sum1){
                 int a = q2.poll();
                q1.add(a);
                cnt++;
                sum2 -= (long) a;
                sum1 +=  (long) a;
            }
        }
        
        
        return cnt;
    }
}