[Java] 프로그래머스 두 큐 합 같게 만들기 (2022 KAKAO TECH INTERNSHIP)

https://school.programmers.co.kr/learn/courses/30/lessons/118667?language=java

프로그래머스

해결방법

• 사용한 알고리즘: 그리디, 투포인터
• 접근 방법:
  • queue1의 합을 sum1, queue2의 합을 sum2라고 했을 때, sum1과 sum2는 다음과 같이 greedy하게 풀 수 있습니다.
    • sum1 > sum2 이면, queue1의 원소를 queue2에 넘겨줍니다.
    • sum2 < sum1 이면, queue2의 원소를 queue1에 넘겨줍니다.
  • 이 방식이 통하는 이유는 다음과 같습니다.
    • sum1 > sum2인 상황에서 sum1을 증가시키고 R을 감소시크는 방법이 최적인 경우가 있다고 가정합시다. sum1 = sum2을 만족시키기 위해서는 결국, sum1을 감소시키고 sum2를 증가시켜야 합니다. 
      • queue2 -> queue1 이후, queue1 -> queue2
      • queue1 -> queue2 이후, queue2 -> queue1
      • 이 두 경우는 결과가 동일(이동하는 횟수)하기 때문에 sum1 > sum2인 상황에서 sum1을 감소시키는 방법이 항상 최적이 될 수 있습니다. 
      • n이 초기 큐의 길이라고 할 경우, 한 포인터당 최대 2n번의 이동이 필요하므로, 총 4*n만큼 반복하면 됩니다.
        • st1과 en2가 같이 움직이고, st2와 en1이 같이 움직이므로 4*2n이 아닌 2*2n번으로 충분합니다.

코드

import java.util.*;

class Solution {
    
    public int solution(int[] queue1, int[] queue2) {
        
        long sum1 = 0;
        long sum2 = 0;
        
        int len = queue1.length + queue2.length;
        int[] arr = new int[len];
        for(int i=0; i<queue1.length; i++) {
            sum1 += queue1[i];
            arr[i] = queue1[i];
        }
        for(int i=queue1.length; i<len; i++) {
            sum2 += queue2[i-queue1.length];
            arr[i] = queue2[i-queue1.length];
        }
        
        if((sum1+sum2) % 2 != 0) {
            return -1;
        }
        
        int st1 = 0;
        int en1 = queue1.length-1;
        int st2 = queue1.length;
        int en2 = len - 1;
        
        int cnt = 0;
        while(cnt <= len*2) {
            
            if(sum1 == (sum1+sum2)/2) {
                return cnt;
            }
            
            if(sum1 > sum2) { // queue1에서 빼기
                sum1 -= arr[st1];
                st1 = (st1+1) % len;
                en2 = (en2+1) % len;
                sum2 += arr[en2];
            } else { // queue2에서 빼기
                sum2 -= arr[st2];
                st2 = (st2+1) % len;
                en1 = (en1+1) % len;
                sum1 += arr[en1]; 
            }
            cnt++;
        }

        return -1;
    }
}

문제리뷰

• 저는 그리디 증명을 못해서, BFS 탐색으로 풀려고 시도하였는데 조건을 잘 고려하지 못해서 틀렸습니다. 
  • 조건을 잘 고려한다고 하더라도 n이 크므로 효율적으로 풀지 못할 것입니다.
  • 문제의 조건에서 n=3*10^5이므로 O(n)이나 O(nlogn)으로 풀 수 있는 알고리즘을 생각하는 방식으로 접근해야겠다는 것을 배웠습니다.