[프로그래머스] 더 맵게 [java]

출처 : programmers.co.kr/learn/courses/30/lessons/42626

코딩테스트 연습 - 더 맵게

ㅍ

풀이

1. 우선순위 큐 

코드

import java.util.*;

class Solution {
    
    static PriorityQueue<Idx> pq ;
    public static class Idx implements Comparable<Idx> {
        int number;
        public Idx(int number){
            this.number = number;
        }
        @Override 
        public int compareTo(Idx o){
            return this.number - o.number;
        }
    }
    public int solution(int[] scoville, int K) {
        int answer = 0;
        pq = new PriorityQueue<>();
        boolean find = false;
        // 1. 우선순위 큐에 순서대로 담기 
        for( int i=0; i<scoville.length; i++){
            pq.add( new Idx( scoville[i]));
        }
        
        while( !pq.isEmpty()){
           
            Idx Min = pq.poll();
            // 2. 가장 작은거 뺏는데 K보다 작으면 
            if ( Min.number < K ){
                if ( pq.isEmpty()) break;
                
                Idx NextMin = pq.poll();
                 // 2. 섞는 과정 : (answer++) 첫번 째 꺼 빼고 + ( 두번째 * 2 )  ==> 그리고 큐에 다시 넣자
                int Comb = Min.number + (NextMin.number*2);
                answer ++;
                pq.add(new Idx(Comb));
            }
            else {
                find = true;
                break;
            }
        }
        
        if( !find ) answer = -1;
        
        
        return answer;
    }
}