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

---

문제 자체는 간단하다.

 

왼쪽 큐 총합이 커지면, 왼쪽 큐 원소를 빼서 오른쪽 큐로 옮기고

 

오른쪽 큐 총합이 커지면 오른쪽 큐 원소를 빼서 왼쪽 큐로 옮기면 된다.

 

그리고[1,4] [4,8] 과 같이 주어지면 무한 루프가 돌 수 있기 때문에, while문 탈출 조건을 (두 큐의 길이 합*2) 이상 반복되면 탈출하도록 설정해놨다.

 

최악의 경우를 가정해서 생각해봤다.

 

큐1 [1 2 3....n] // 큐 2 [1 2 3 ....m]

큐1 [n] // 큐 2[1 2 3 ...m 1 2 3....n-1]  (약 n-1번 소요)

큐1[1 2 3 ....m] // 큐2[1 2 3 ....n]  (약 m+1번 소요)

 

큐 1과 큐2의 원소가 완전히 바뀌려면 n+m번이 소요되고

다시 큐1이 처음 큐1원소로 돌아가려면 n+m번이 더 소요되어 총 2(n+m)번이 소요될 것이다.

큐1과 큐2 길이는 초기에 같은 값으로 주어지므로 4*(n) 번을 탈출 조건으로 두면 된다.

 

큐1이 돌고 돌아 다시 큐1원소로 돌아갔다는 뜻은 답이 존재하지 않는 다는 뜻일테니 탈출 조건으로 설정하였다.

 

import java.util.*;
class Solution {
    Queue<Integer> left = new LinkedList<>();
    Queue<Integer> right = new LinkedList<>();
    long leftSum = 0;
    long rightSum = 0;
    public int solution(int[] queue1, int[] queue2) {
        int answer = 0;
        setUp(queue1,queue2);

        while(leftSum!=rightSum){
            if(answer>4*(queue1.length)){
                return -1;
            }
            if(leftSum>rightSum){
                int move = left.poll();
                right.offer(move);
                leftSum-=move;
                rightSum+=move;
            }else if(leftSum<rightSum){
                int move = right.poll();
                left.offer(move);
                leftSum+=move;
                rightSum-=move;
            }
            answer++;
        }
        return answer;
    }
    
    void setUp(int[] queue1, int[] queue2){
        for(int i=0;i<queue1.length;i++){
            left.offer(queue1[i]);
            leftSum+=queue1[i];
            
            right.offer(queue2[i]);
            rightSum+=queue2[i];
        }    
    }
}