두 큐 합 같게 만들기(프로그래머스)

https://school.programmers.co.kr/learn/courses/30/lessons/118667

프로그래머스

 

요구사항 분석

1. queue1의 요소들의 합과 queue2의 요소들의 합을 같게 만들어라.

2. queue는 배열의 형태로 제공됨.

3. queue1, queue2 중 한 큐에서 'pop() 후 insert()'의 과정을 하나의 work라 취급

4. queue1, queue2의 길이는 최악의 경우 300000

5. queue1, queue2의 원소의 크기는 최악의 경우 10^9

 

사고의 흐름

문제를 읽고 가장 먼저 떠올린 알고리즘은 그리디 알고리즘과 dp이다.

모든 경우를 다 살펴 봐야 한다면 dp이고(혹은 완전 탐색을 해야한다면??),

현재의 선택이 최적해면 그리디라고 생각.

즉, 그리디임을 만족하면 그리디를 쓰고, 그리디가 아니면 dp를 쓴다.(dp로 해도 되긴하지만...)

 

우선, 입출력 예시에 나온 경우들은 모두 그리디 방식을 적용해 보았을때, 쌉가능.

그리디임을 확인하기 위해 생각을 진행.

queue1을 기준으로 생각

작업 : 'queue1의 원소의 합' > 'queue2의 원소의 합' 이라면 queue1의 원소를 뺌(queue2에 그걸 더함)

'queue1의 원소의 합' <= 'queue2의 원소의 합'이 될 수 있음. cnt는 +1이 필요

즉, 저렇게 하면 cnt+1에 같아질 확률이 있음

 

'queue1의 원소의 합' > 'queue2의 원소의 합'이지만, queue2의 원소를 queue1에 더하는 것이 최적합이라면,

그렇게 진행 cnt+1

'queue1의 원소의 합' > 'queue2의 원소의 합'은 변하지 않아, queue1의 요소를 빼는 cnt+1이 필요함.

즉, 같아질 확률이 없음.

cnt의 측면에서는 후자의 방법이 cnt+2가 되는 결과를 가져옴.

결국, cnt+1인 위의 방법이 최적합임. 

 

그리디임!

배열의 형태를 queue와 같이 다루기에는 코딩실력이 형편 없으니 queue를 만들어 담자!(시간 복잡도도 괜찮다.)

queue1의 것을 빼는 것은 queue2에 더하는 것이고, queue1을 더하는 것은 queue2를 빼는 것이므로 queue1만 집중.

원소의 크기가 10^9이므로, long을 고려. 걍 long으로 합을 설정.

 

코드

import java.util.*;
class Solution {
    private Queue<Integer> rQueue1 = new LinkedList<>();
    private Queue<Integer> rQueue2 = new LinkedList<>();
    public int solution(int[] queue1, int[] queue2) {
        fillQueue(queue1, queue2);
        int answer = work(queue1, queue2);
        return answer;
    }
    public void fillQueue(int[] queue1, int[] queue2){
        for(int i = 0; i < queue1.length; i++){
            rQueue1.add(queue1[i]);
            rQueue2.add(queue2[i]);
        }
    }
    public int work(int[] queue1, int[] queue2){
        long sum = getSum(queue1);
        long targetNum = getTargetNum(sum, queue2);
        int cnt = 0;
        for(int i = 0; i < queue1.length * 3; i++){
            if(sum > targetNum){
                int n = rQueue1.poll();
                rQueue2.add(n);
                sum -= n;
                cnt++;
                continue;
            }
            if(sum < targetNum){
                int n = rQueue2.poll();
                rQueue1.add(n);
                sum += n;
                cnt++;
                continue;
            }
            if(sum == targetNum){
                return cnt;
            }
        }
        return -1;
    }
    public long getSum(int[] queue1){
        long sum = 0;
        for(int i = 0; i < queue1.length; i++){
            sum += queue1[i];
        }
        return sum;
    }
    public long getTargetNum(long sum, int[] queue2){
        long targetNum = sum;
        for(int i = 0; i < queue2.length; i++){
            sum += queue2[i];
        }
        return sum / 2;
    }
}