[프로그래머스] 두 큐 합 같게 만들기 for JAVA

 

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

프로그래머스

 

 

문제

 

 

---

 

 

문제를 보고 약간 당황한 문제이다.

 

 

문제 자체의 이해는 쉽다. 

 

문제를 보고 특정 알고리즘이 그닥 떠오르지 않았다.

 

 

이게 그리디하게 풀리지 않는다면.. 내가 풀 수 없는 어떤 알고리즘을 사용하는거거나 엄청난 수학 문제구나 생각함.

 

결론부터 말하자면 그리디가 맞았다.

 

 

두 큐가 숫자를 계속 옮겨갈건데 그리디하게 한쪽이 크면 작은 쪽으로 옮기는 방식을 선택했고

 

 

가장 고민했던 부분은 어떤 방법으로도 원소 합을 같게 만들 수 없다는 것을 알려면 여러번 하다가 특정 조건에서 멈춰야함

 

이 조건에 대해 고민을 많이 했다.

 

 

그리고 다른사람꺼 슬쩍 봤다 ㅎㅎ

 

queue1과 2에서 각각이 자신이 가지고 있던 원소 개수보다 2배 이상 빼내면 끝내는걸로 하였다.

 

꼭 2배여야하는건 아니고 대강 잡은듯

 

 

풀이의 결론은 그리디하게! 큰곳 -> 작은곳

 

 

코드

import java.util.*;
import java.io.*;

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        // 그리디하게 풀어야지
        // 두 배열의 총합을 구한다.
        long hap1=0, hap2=0;
        int size = queue1.length;
        
        // 두 배열을 큐에 넣기
        Queue<Integer> q1 = new ArrayDeque<>();
        Queue<Integer> q2 = new ArrayDeque<>();
        
        for(int i=0; i<size; i++){
            hap1 += queue1[i];
            hap2 += queue2[i];
            q1.add(queue1[i]);
            q2.add(queue2[i]);
        }
        // 만들어야 하는 수
        long goal = (hap1+hap2)/2;
        
        // 합이 홀수이면 -1출력
        if((hap1+hap2)%2 == 1){
            return -1;
        }
        
        int cnt1 = 0, cnt2 = 0; // 각각의 큐에서 빼낸 횟수 (=움직인 횟수)
        // 빼낸 횟수가 본인이 가지고 있던것보다 적어야함
        while(cnt1 <= size*2 && cnt2 <= size*2){
            // 양쪽 합이 goal과 같다면 끝낸다.
            if(hap1 == goal && hap2 == goal){
                return cnt1+cnt2;
            }     
            
            // 큰쪽에서 작은 쪽으로 움직인다.
            if(hap1 > hap2){
                int out = q1.poll();
                q2.add(out);
                hap1 -= out;
                hap2 += out;
                
                cnt1 += 1;
            } else{
                int out = q2.poll();
                q1.add(out);
                hap1 += out;
                hap2 -= out;
                
                cnt2 += 1;
            }
        }
        
        return -1;
        
    }
}

 

 

성능

 

 

다른 사람들도 이렇게 풀었다.