그리디

프로그래머스 2022 KAKAO TECH INTERNSHIP Level 2 문제 두 큐 합 같게 만들기를 Java를 이용해 풀어보았다.
최적의 해를 구하기 위해 규칙 하나를 만들어서 풀어나가면 답이 나오는 형태다.

문제 링크 첨부한다.
https://school.programmers.co.kr/learn/courses/30/lessons/118667

규칙 만들기

처음에 만났을 때는 시간초과가 나고 실패하는 테스트 케이스들도 있었다. 이번이 두 번째 시도였는데 안타깝게 첫 번째에 어떻게 풀었는지 반 년이나 지났지만 기억이 나서... 왜 그렇게 풀어야만 하는지 스스로에게 설명하며 정당성을 부여해 나가며 원리를 이해하려 했다.
하지만 사실 원리라고 할 것까지도 없는 문제긴 하다.

결국 합을 같게 만들어주기 위해서는 반드시 합이 큰 큐에서 작은 큐로의 원소 이동이 필요하기 때문에 매순간 두 큐의 합의 대소를 비교해가며 이동시키면 된다.

루프 탈출 조건은 문제에 나와있는 조건을 그대로 적어주는 것. 추가로 신경써야 하는 부분은 언제까지 서로 원소 이동을 시킬 것이냐?
이 부분은 다시 원상복구가 되는 순간인 원래 큐 길이 * 4 로 보통 잡던데 나는 그냥 3으로 잡아줬는데 다 통과가 됐다. 3으로 잡았을 때까지 마무리가 되지 않았으면 문제 목적을 달성할 수 없는 상태라고 판단해서 3으로 했는데 통과가 됐다.

다음은 내가 제출한 코드다.

public class 두큐합같게만들기 {

    public static void main(String[] args) {
        int[] queue1 = {1,2,1,2};
        int[] queue2 = {1,10,1,2};
        System.out.println(solution(queue1, queue2));
    }

    static int solution(int[] queue1, int[] queue2){
        int totalNum = 0;
        long qSum1 = 0;
        long qSum2 = 0;
        Queue<Integer> q1 = new LinkedList<>();
        Queue<Integer> q2 = new LinkedList<>();

        for(int n: queue1) {
            qSum1 += n;
            totalNum++;
            q1.add(n);
        }
        for(int n: queue2) {
            qSum2 += n;
            totalNum++;
            q2.add(n);
        }

        if((qSum1 + qSum2)%2!=0)    return -1;

        int cnt = 0;
        while(true){
            int tmp;
            if(q1.isEmpty() || q2.isEmpty())    return -1;

            if(qSum1>qSum2){
                tmp = q1.poll();
                q2.add(tmp);
                qSum1 -= tmp;
                qSum2 += tmp;
            }
            else if(qSum2>qSum1){
                tmp = q2.poll();
                q1.add(tmp);
                qSum1 += tmp;
                qSum2 -= tmp;
            }
            else    break;

            cnt++;
            if(cnt>=totalNum + totalNum/2) return -1;
        }

        return cnt;
    }
}

반드시 복잡한 알고리즘을 적용시켜야만 풀릴 거라는 이상한 편견을 좀 내려놓고 가장 단순한 질문인 어떻게 해결할 수 있을까? 부터 먼저 스스로에게 묻는 연습을 해야겠다.
오랜만에 알고리즘을 풀어봤는데 다시 매일 꾸준히 1문제씩 푸는 습관을 들여보려 한다.... 험난하다...