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

문제

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

프로그래머스

 

---

해설

두 큐를 한 요소씩 이동하며 같은 합이 나오는 최소한의 횟수를 구하는 문제입니다. 

큐의 특징상 들어가고 나오는 순서가 정해져있어 임의의 요소를 옮길 수 없습니다. 따라서 반복을 통해 결과를 도출해야합니다.

 

두 큐의 합이 같아지도록 만들기 위해 반복되는 내부에서는 큐의 합이 더 큰 쪽에서 작은 쪽으로 한 값씩 이동하며 비교해 줍니다.

반복을 멈추는 조건으로는 두 큐의 합이 같거나, 모든 가능성을 파악한다, 2가지로 정리해 볼 수 있습니다.

두 큐를 서로 이동 할 때 처음 상태로 돌아가기 위해서는 최대  (큐1의 길이 + 큐2의 길이) *2만큼 필요합니다.

 

위 정보들을 정리해 답을 구해낼 수 있습니다.

주의점

• 두 큐의 합이 같으려면 입력으로 주어진 값들의 합이 짝수여야 가능하고 홀수라면 -1로 return한다
• 두 큐를 서로 이동할 때 처음 상태로 다시 돌아가는 최악의 횟수는 (큐1의 길이 + 큐2의 길이) *2 가 된다.
• 연산중 값이 int범위 이상으로 커질 수 있어 long타입을 사용한다.

---

코드

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,sum2=0;
        for(int i=0;i<queue1.length;i++){
            q1.offer(queue1[i]);
            sum1 += queue1[i];
            q2.offer(queue2[i]);
            sum2 += queue2[i];
        }
        //총합이 홀수인 경우 같게 만들기 불가능
        if((sum1+sum2)%2==1)return -1;
        
        int move=0;
        // 두 합이 같거나 모든 경우를 확인한 경우 while탈출
        while(sum1!=sum2 && answer<=4*queue1.length){
            if(sum1>sum2){
                move = q1.poll();
                sum1 -= move;
                sum2 += move;
                q2.offer(move);
            }else if(sum2>sum1){
                move = q2.poll();
                sum2 -= move;
                sum1 += move;
                q1.offer(move);  
            }
            answer++;
        }
        // 모든 경우를 보았지만 실패한 경우
        if(sum1!=sum2)return -1;
        return answer;
    }
}