[그리디] Kakao - 두 큐 합 같게 만들기

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

프로그래머스

 

 

접근 알고리즘 개념 - 그리디 
탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법으로,여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달 합니다.

->while(true)로 돌면서 제약조건을 걸어 최적의 해를 도출한다.

 

문제 해결 - 최적해를 구하기 위한 결정 포인트 정리
     1. 모든 원소의 합이 홀수인 경우는 큐의 원소 합이 같을 수가 없으므로 제외.

     2. 2번째 종료조건을 "작업횟수 > (1번큐길이+2번큐길이)*2"로 한다.
        "작업횟수 > (1번큐길이+2번큐길이)+1" 도 문제에선 통과가 가능하다.  

 

        최대 작업횟수에 대해서는 여러 의견이 있는데,

        위 문제에서는 일단 두 큐의 길이보다 1이라도 더 크게 잡으면 통과하도록 잡은 것 같다.

        중요한건 2개의 큐길이 합 만큼만 순회 시킨다면 반례가 존재하기 때문에

        무조건 길이의 합보다 크게 잡아야 한다는 것이다.

     3. 양쪽을 다 계산하는 것은 비효율적이므로 한쪽의 합이 전체의 반인 경우 결과값인 것으로 판단한다.
     

    4. 합의 크기에 따라 더할지 뺄지를 정합니다.

    

    5. 제한사항에서 큐들의 길이가 최대 300,000이다. 따라서 O(n) - 1000만~2000만으로 해결이 가능하다.

 

import java.util.*;
class Solution {
    public int solution(int[] queue1, int[] queue2) {
        int answer = 0;
        long total = 0; // 두 큐의 합
        long q1sum = 0; // 1번 큐의 합
        
        Queue<Integer> q1 = new LinkedList<>();
        Queue<Integer> q2 = new LinkedList<>();

        for(int i=0;i<queue1.length;i++){
            total += queue1[i]+queue2[i];
            q1sum += queue1[i];
            
            q1.add(queue1[i]);
            q2.add(queue2[i]);
            }
        
        if(total%2!=0){    // 두큐의 모든 원소의 합이 홀수일 경우 같게 못만듬. 
            return -1;
        }
        
        long target = total/2;  	// 두큐의 합이 같을경우, 한쪽 큐의 합
        
        while(true){
            if(q1sum == target){    // 두큐의 합이 같아지면 종료
                break;
            }
            if(answer > (queue1.length+queue2.length)*2){     //두큐의 합이 같을 수 없을경우
                return -1;
            }
            
            else if(q1sum>target){
                q1sum = q1sum - q1.peek();
                q2.add(q1.poll());
            }
            else{   // q1sum < target
                q1sum = q1sum + q2.peek();
                q1.add(q2.poll());
            }
            answer++;
        }
        
        return answer;
    }
}