프로그래머스 - 더 맵게(Java)

 

문제 이해가 어렵지 않은 문제이고 최소힙 구현만 한다면 쉽게 풀 수 있는 문제이다.

 

https://developerwoohyeon.tistory.com/163

[Java] PriorityQueue를 활용한 힙(Heap) 구현

 

문제 해결

 

 

우선 scoville 배열의 모든 숫자를 우선순위 큐에 삽입해준다.

 PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        int answer = 0;
        for(int sc : scoville){
            minHeap.offer(sc);
        }

 

 

이때 스코빌 지수의 최소값이 K 이상이면 스코빌 지수를 K이상으로 만들 필요가 없으므로 answer를 그대로 반환.

if(minHeap.peek()>=k){
            return answer;
}

 

 

while문 에서 최소값 min1과 그 다음으로 낮은 값 min2를 힙에서 뽑아내고 min1+min2*2를 힙에 다시 삽입해준다.

 

만약 힙의 크기가 2 이하이면 스코빌 지수를 섞을 수 없기 때문에 -1을 리턴해준다. 

while(minHeap.peek()<k){
            if(minHeap.size()<2){
                return -1;
            }
            else{
            int min1 = minHeap.poll();
            int min2 = minHeap.poll();
                int mix=min1+min2*2;
                minHeap.offer(mix);
                answer++;
            
        }
        
    }
        return answer;

 

 

 

<전체 코드>

import java.util.*;

class Solution {
    public int solution(int[] scoville, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        int answer = 0;
        for(int sc : scoville){
            minHeap.offer(sc);
        }
        if(minHeap.peek()>=k){
            return answer;
        }
        
        while(minHeap.peek()<k){
            if(minHeap.size()<2){
                return -1;
            }
            else{
            int min1 = minHeap.poll();
            int min2 = minHeap.poll();
                int mix=min1+min2*2;
                minHeap.offer(mix);
                answer++;
            
        }
        
    }
        return answer;
}
}