프로그래머스 두 큐 합 같게 만들기 java//Queue pop==poll push==offer, 그리디

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

프로그래머스

 

* 문제해결과정

1. 관찰

2. 항상 큐의합이 많은곳에서 적은곳으로 옮겨야한다.

3. 옮기다보면 언젠가는 정답이되고 , 그때의 정답의 최적해이지 않을까? (그리디)

4. 단, 불가능한경우의 종료조건을 찾아야한다.

종료조건 : 총 pop을 4*n(큐의크기)번만큼 햇는데도 못찾은경우

[1,2,3,4] 에서 pop 을 4번-> [ 빈 칸 ]

다시 pop되서 옴 -> [1,2,3,4] (8번) -> 1번큐에서 2n번 pop ->2번큐도 2n번 팝됫음

총pop이 4n이상 -> 초기상태로 원복됫는데도 정답이안됨 -> 불가능.

 

* 의사코드

1. 총합, 각각합을 구한다

2. 무한루프를 돌면서

합이 큰쪽에서 작은쪽으로 pop(poll), push(offer)한다.

동시에 sum1, sum2 도 갱신한다. 

※ (큐를 반복문돌며 갱신하면 시간초과난다. -> 즉시갱신)

한루프가 끝나면 answer++

 

종료조건 : 합이 딱 반씩된경우 , 불능인경우

 

* 정답코드

import java.util.*;

class Solution {
    static Queue<Integer> q1=new LinkedList<>();
    static Queue<Integer> q2=new LinkedList<>();
    static int answer;
    static long sum1;
    static long sum2;
    static long total;
    
    public int solution(int[] queue1, int[] queue2) {
        
        for(int i : queue1){
            q1.add(i);
            sum1+=i;
            total+=i;
        }
        for(int i : queue2){
            q2.add(i);
            sum2+=i;
            total+=i;
        }
        
        //System.out.println("목표: "+total/2);
        //System.out.println(sum1);
        //System.out.println(sum2);
        // for(int item : queue1){
        //     System.out.println(item);
        // }
        // for(int item : queue2){
        //     System.out.println(item);
        // }
        //##############입력테스트 완료##################
        
        while(true){
            if(sum1==total/2 && sum2==total/2 && sum1==sum2){
                break;
            }
            if(answer>=4*queue1.length) return -1;
            
            //System.out.println("sum1: "+sum1);
            //System.out.println("sum2: "+sum2);
            if(sum1>sum2){
                int temp=q1.poll();
                q2.offer(temp);
                sum1-=temp;
                sum2+=temp;
                //System.out.println("temp: "+temp);
            }
            else if(sum1<sum2){
                int temp=q2.poll();
                q1.offer(temp);
                sum1+=temp;
                sum2-=temp;
                //System.out.println("temp: "+temp);
            }
            
            //#########sum 갱신###################
            // sum1=0;
            // sum2=0;
            // for(int i : q1){
            //     //q1.add(i);
            //     sum1+=i;
            //     //total+=i;
            // }
            // for(int i : q2){
            //     //q2.add(i);
            //     sum2+=i;
            //     //total+=i;
            // } 시간초과 -> sum갱신시 반복문 필요없음.
            
            
            answer++;
        }
        
        
        return answer;
    }
}