두 큐 합 같게 만들기 (Java, Greedy + Queue, 프로그래머스(카카오))

복잡한듯 복잡하지 않은 문제였다.

카카오 공식 풀이에서는 그리디와 투포인터 2가지 해결 방법을 제시한다.

 

풀이 아이디어를 얻기까지는 꽤 어려웠으나

단순하게 한쪽 큐의 전체합이 최적해가 되는지만 판별하는 그리디라는 문제라는 것을 알고나서 구현하는 것은 매우 쉬웠다.

그리디 문제인지를 알아채기는 힘들지만 찾고나면 구현하기는 쉽다는 점이 그리디 문제의 특징인 것같다. 

 

맨 처음 풀이는 아래 코드보다 시간복잡도가 좋지않게 풀었으나 단순 순회를 여러번 반복하는 것뿐이라 통과 자체에는 문제가 생기지 않았다.

 

import java.util.*;

class Solution {
    //시간복잡도 nlogn 제한
    int helper(LinkedList<Long> q1, LinkedList<Long> q2, long q1Sum, long q2Sum) {
        var count = 0;
        
        var sum = q1Sum + q2Sum;
        if (sum % 2 == 1) return -1;
        var length = q1.size() + q2.size();
        //부분합의 최대 구하기.
        while (true) {
            //count가 30만 + 30만 = 60만을 넘어가면 범위 내에서 최적해 불가능.
            if (count > 600001) {
                return -1;
            }
            //q1의 합이 전체/2와 같아지면 
            if (q1Sum == sum/2) {
                return count;
            //q1의 합이 전체/2보다 크다면 
            } else if (q1Sum > sum/2) {
                var poll = q1.poll();
                q2.offer(poll);
                
                q2Sum += poll;
                q1Sum -= poll;
            //q1의 합이 전체/2보다 작으면
            } else if (q1Sum < sum/2) {
                var poll = q2.poll();
                q1.offer(poll);
                
                q1Sum += poll;
                q2Sum -= poll;
            }
            count++;
        }
        
    }
    public int solution(int[] queue1, int[] queue2) {
        var q1 = new LinkedList<Long>();
        var q2 = new LinkedList<Long>();
        var q1Sum = 0L;
        var q2Sum = 0L;
        for (var i : queue1) {
            q1.offer((long)i);
            q1Sum += (long) i;
        }
        for (var i : queue2) {
            q2.offer((long)i);
            q2Sum += (long) i;
        }
        
        return helper(q1, q2, q1Sum, q2Sum);
    }
}