[프로그래머스]heap-더 맵게

• 직접 짠 풀이

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> spicier = new PriorityQueue<>();
        PriorityQueue<Integer> maxCheck = new PriorityQueue<>(Comparator.reverseOrder());

        for(int i=0; i<scoville.length; i++){
            spicier.add(scoville[i]);
        }
        for(int i=0; i<scoville.length; i++){
            maxCheck.add(scoville[i]);
        }
        if(K==0) return 0;
        if(maxCheck.isEmpty() || maxCheck.peek()==0){
            return -1;
        }

        int s1=0, s2=0;
        while(!spicier.isEmpty() && spicier.peek()<K){
            if(spicier.size()==1) return -1;
            s1 = spicier.poll();
            if(spicier.isEmpty()){
                spicier.add(s1*2);
            } else {
                s2 = spicier.poll();
                spicier.add(s1 + s2*2);
            }
            answer++;
        }

        return answer;
    }
}

java 내장 클래스 PriorityQueue는 heap으로 만들어졌다는 사실을 며칠전에 알고 이를 이용.

직접 짜긴 했는데 정답 코드들 보니 너무 간결.. 나는 예외처리를 하다보니 코드가 너무 더러워졌다. 다시 깔끔하게 짜야지

• 두번째 풀이

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> spicier = new PriorityQueue<>();

        for(int i=0; i<scoville.length; i++){
            spicier.add(scoville[i]);
        }

        while(spicier.size()>1 && spicier.peek()<K){
            spicier.add(spicier.poll() + spicier.poll()*2);
            answer++;
        }

        return spicier.peek() >= K? answer : -1;
    }
}

예외처리를 깔끔하게 한 풀이.

알고리즘

1. 우선순위 큐에 scoville을 담는다.
2. 큐의 size가 2이상이고 K 이하인 음식이 남아있을 때 가장 안 매운 음식과 두번째로 안 매운 음식을 합쳐 scoville을 보정한다. 그리고 answer을 increment한다.
3. 큐 안에 scoville 지수가 K를 넘지 않는 음식이 존재한다면 -1을 return하고 존재하지 않으면 정상적으로 answer를 return한다.