[프로그래머스] 두 큐 합 같게 만들기 (자바)

두 큐 합 같게 만들기

문제풀이

두 개의 큐를 선언하고 하나의 큐를 골라 원소를 다른 큐에 집어넣는 작업을 진행한다.

이 작업을 한 번 하면 횟수가 하나 올라가며 작업의 최소 횟수를 구해야 한다.

만약 queue1에 요소들의 합이 queue2보다 크다면 queue1에서 pop한 요소를 queue2에 add 하면 되고, 그 반대면 queue2에서 pop한 요소를 queue1에 add하는 작업을 진행하면 된다.
최대 진행 횟수를 queue1의 길이에 대략 2배 정도로 설정하면 모든 경우의 수(worst case)를 진행할 수 있을 것 같다.
그런데 나의 경우 2배로 설정을 하니까 1번 테스트코드에서 실패가 떴는데 3배로 수정을 하니까 해결이 됐다. 만약, 채점하기의 1번 테스트 케이스에서 실패가 뜬다면 최대 진행 횟수를 3배로 수정해보자.

추가로 두 큐의 모든 요소의 합이 홀수인 경우와 특정 요소가 두 큐의 모든 요소의 합의 절반보다 큰 경우에 -1을 return 하는 조건문을 만들어주었다.

구현코드

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 sum1 = 0;
        long sum2 = 0;
        long count = 0;
        
        for(int i = 0; i<queue1.length; i++){
            sum1+=queue1[i];
            sum2+=queue2[i];
        }
        
        long totalSum = sum1+sum2;
        
        if(totalSum%2==1){
            answer = -1;
            return answer;
        }
        
        for(int i = 0; i<queue1.length; i++){
            if(queue1[i]>totalSum/2||queue2[i]>totalSum/2){
                answer=-1;
                return answer;
            }
        }
        
        
        for(int i = 0; i<queue1.length; i++){
            q1.add(queue1[i]);    
            q2.add(queue2[i]);
        }
        
        long limitLen = queue1.length * 3;
        
        while(sum1!=sum2){
            if(count > limitLen){
                answer = -1;
                break;
            }
            
            if(sum1>sum2){
                sum1 -= q1.peek();
                sum2 += q1.peek();
                q2.add(q1.poll());
                count++;
                answer++;
            }
            else{
                sum2 -= q2.peek();
                sum1 += q2.peek();
                q1.add(q2.poll());
                count++;
                answer++;
            }
        }
        
        // answer = count.intValue();
        return answer;
    }
}

long limitLen (최대 진행횟수)를 어떻게 설정할 것인지가 이 문제의 키포인트라고 생각한다. 문제를 많이 풀면서 이런 부분에 대해서 감을 잡아가는게 중요할 것 같다.