[Programmers] 두 큐 합 같게 만들기

문제 파악

1. 두 개의 큐 값을 같게 만들어야한다.
2. 두 개의 큐의 값이 같기 전에는 한 개의 큐는 작고 한 개의 큐는 클 것 이다.
3. 큐는 FIFO로 먼저 들어온 것이 먼저 나간다. 즉, 두 개의 큐에서 한 번의 이동에 나올 수 있는 숫자는 제일 앞에 있는 숫자이다.
4. 큰 큐의 값을 하나빼서 작은 큐에 옮기는 것을 반복하여 두 큐가 같도록 한다.
4. 단 카운트가 두 큐 사이즈의 합 *2를 넘긴 경우 두 큐가 같아 지는 경우가 없으므로 -1을 반환
5. 1 ≤ queue1의 원소, queue2의 원소 ≤ 10^9 이므로 큐의 합은 int의 최대값 넘을 수 있다. 따라서 큐의 합은 long 타입으로 선언.

접근 방법

1. 두 개의 큐를 선언 하고 int[]을 순환하며 큐에 값을 넣고 각각의 큐에 들어간 원소의 합을 구한다.
2. 두 큐의 값을 비교한다.
3-1. 만약 한 쪽 큐의 합이 크고 다른 쪽의 합이 작으면 큰 쪽 큐의 제일 앞 수를 remove해서 다른 큐에 add해준다.
3-2. 만약 두 큐의 합이 같으면 count를 반환한다.
3-3. 만약 count가 두 큐의 크기 *2 가 넘어가면 -1을 반환한다.

코드 구현

import java.util.*;
class Solution {
    public int solution(int[] queue1, int[] queue2) {
        Deque<Integer> q1 = new ArrayDeque<>();
        Deque<Integer> q2 = new ArrayDeque<>();
        long sumq1 = 0;
        long sumq2=0;
        int count=0;
        for(int i : queue1){
            sumq1+=i;
            q1.add(i);
        }
        for(int i : queue2){
            sumq2+=i;
            q2.add(i);
        }
        while (true){
            if(sumq1 ==sumq2){
                break;
            }
            else if(count>=(queue1.length+queue2.length)*2){
                count=-1;
                break;
            }
            else if(sumq1>sumq2){
                int number = q1.remove();
                sumq1 -=number;
                sumq2 += number;
                q2.add(number);
            }
            else{
                int number = q2.remove();
                sumq2 -=number;
                sumq1 += number;
                q1.add(number);
            }
            count++;
        }

        return count;
    }
}

코드 구현(오답)

💡 실패한 사례

sumq1, sumq2를 int로 선언 : 오류 발생 ⇒ queue1의 원소 값이 int 의 범위를 넘어가는 경우가 있어서 오류 발생 ⇒ sumq1, sumq2를 long 타입으로 선언

import java.util.*;
class Solution {
    public int solution(int[] queue1, int[] queue2) {
        Deque<Integer> q1 = new ArrayDeque<>();
        Deque<Integer> q2 = new ArrayDeque<>();
        int sumq1 = 0; //오답의 원인
        int sumq2=0; //오답의 원인
        int count=0;
        for(int i : queue1){
            sumq1+=i;
            q1.add(i);
        }
        for(int i : queue2){
            sumq2+=i;
            q2.add(i);
        }
        while (true){
            if(sumq1 ==sumq2){
                break;
            }
            else if(count>=(queue1.length+queue2.length)*2){
                count=-1;
                break;
            }
            else if(sumq1>sumq2){
                int number = q1.remove();
                sumq1 -=number;
                sumq2 += number;
                q2.add(number);
            }
            else{
                int number = q2.remove();
                sumq2 -=number;
                sumq1 += number;
                q1.add(number);
            }
            count++;
        }

        return count;
    }
}

배우게 된 점

💡 두 큐의 합을 구할 때 막연히 더하고 빼는 것이 아니라 최적의 경우를 생각해보고 푸는 것이 좋을 것 같다.
    또한, 문제에서 값의 범위를 확인하여 변수의 타입을 설정하는 습관을 길러야할 것 같다.