99클럽 코테 스터디 8일차 TIL + Programmers 두 큐의 합 같게 만들기 (java)

1. 문제 설명

문제 링크

2. 접근 방식

KEY WORD: GREEDY

1. 문제 설명 그대로 Queue 두 개를 만든다.
2. 총합이 큰 쪽의 queue.peek()을 poll 해서 다른 쪽 큐에 추가한다.
3. 2번 종료 후 두 큐의 총합이 같은지 검사한다.
4. 만약 같으면, 2번을 행한 횟수를 출력한다. 만약 두 큐의 총 길이 + 1 만큼 해도 두 큐의 합이 같지 않으면 -1을 출력하고 종료 한다.

두 큐의 총 길이 + 1 만큼 반복해야 하는 이유는 뒤에서 설명.

3. 코드 분석

import java.io.*;
import java.util.*;

class Solution {
    public int solution(int[] queue1, int[] queue2) {

        ArrayDeque<Integer> a = new ArrayDeque<>();
        ArrayDeque<Integer> b = new ArrayDeque<>();
        // sum == 각 큐의 합, cnt == 작업 횟수
        long sumA = 0;
        long sumB = 0;
        int cnt  = 0;

        for(int i = 0; i < queue1.length; i++){
            a.add(queue1[i]);
            b.add(queue2[i]);
            sumA += queue1[i];
            sumB += queue2[i];
        }

        if((sumA+sumB)%2 == 1) return -1;
        // 그 때 그 때 매번 sum을 구하지 말고, 하나 구해놓고 +,-로 조정한다. 
        while(sumA != sumB){
            // 기저 조건
            if(cnt > (queue1.length + queue2.length)+1) {
                cnt = -1; 
                break;
            }

            if(sumA > sumB){
                int now = a.poll();
                sumA -= now;
                sumB += now; 
                b.add(now);
            }

            else if(sumB > sumA){
                int now = b.poll();
                sumB -= now;
                sumA += now;
                a.add(now);
            }
            cnt++;
        }

        return cnt;
    }
}

4. 성장 하기

(1) 해당 문제에서 원소의 최대 크기는 10^9이었다. 따라서 총합을 구할 시, int형의 최대값인 21억을 넘을 수 있다.
sum의 자료형은 int가 아니라 Long으로 해야한다.
-> 해당 부분을 자주 간과해서, 맞는 코드를 작성하고도 해메는 경우가 많다. 자료형이 변수의 값을 감당할 수 있는지를 항상 체크하자.

(2) 반복문이 queue의 길이의 합 + 1 만큼 반복되어야 하는 이유
Input을 다음과 같이 넣어보자.

queue1	queue2	result
[3,3,3,3]	[3,3,27,3]	9

해당 값이 서로 27로 일치하기 위해서는 9번의 움직임이 필요하다. 따라서 queue의 길이의 총합 보다 좀 더 넉넉히 가져가야 한다. 이것을 반례 전에 파악할 수 있는 방법이 있는지는 아직 잘 모르겠다.
다음에 코딩 테스트에서도 일부 틀릴 경우, 이러한 반례가 있을 경우를 대비해 반복문의 길이를 시간 초과가 안나는 선에서 넉넉히 가져가는 방법을 고려하자.