두 큐 합 같게 만들기

문제

풀이

문제 자체는 되게 간단했는데 고려해야하는 부분이 몇개 있어 까다로웠던 문제다

문제 자체는 그냥 한 쪽 큐가 더 커졌을 때 실제로 카드를 옮겨주는걸 반복만 하면 된다.

여기서 고려해야할 부분은 한가지다.

불가능하다는 판정을 어떻게 내릴것인가?

방법은 간단하다. 이 문제에서 queue에서 꺼내는 방법은 무조건 FIFO 방식이므로 어떤 방식으로 교환을 해도 큐 길이의 3배 안에 모든 경우의 수를 확인하게 되어있다. 즉 count가 que 길이의 3배를 넘어가게 되면 바로 불가능하다고 판정하고 동작을 멈춰도 되는 것이다.

import java.util.*;
class Solution {
    public int solution(int[] queue1, int[] queue2) {
        int answer = -2;
        int count = 0;
        int tmp = -1;
        int len = queue1.length;
        Queue<Integer> que1 = new LinkedList<>();
        Queue<Integer> que2 = new LinkedList<>();
        //각각 큐1, 큐2의 합
        long sum1 = 0,sum2 = 0;
        
        //각 큐에 카드 넣기
        for(int i=0; i<len; i++){
            sum1 += queue1[i];
            que1.offer(queue1[i]);
            sum2 += queue2[i];
            que2.offer(queue2[i]);
        }
        

        //조건이 만족되지 않았다면
        while(sum1 != sum2){
            
            //카드 옮기기
            if(sum1 > sum2){
                tmp = que1.poll();
                sum1 -= tmp;
                que2.offer(tmp);
                sum2 += tmp;
            }else{
                tmp = que2.poll();
                sum2 -= tmp;
                que1.offer(tmp);
                sum1 += tmp;
            }
            count++;
            //불가능 판정
            if(count>len*3) return -1;
        }
        
        answer = count;
        return answer;
    }
    

}

처음 for문을 통해 주어진 배열을 큐에 넣어주고 while문을 통해 조건이 만족 될때까지 카드를 옮기는 동작을 수행했다. 이때 아까 말한대로 count가 len의 3배를 넘어가면 멈추도록 조건을 걸어두었다.

여기서 한가지 더 주의할 점이 있는데 문제의 제한사항에 적혀있듯 합 계산 과정 중 산술 오버플로우가 발생하게 되어 sum의 타입을 long이 아닌 int로 선언하면 몇몇 케이스에서 실패가 나오게 되니 주의해야한다.