[JAVA] 힙 "더 맵게"

이 문제는 힙을 이용하는 원리인데, JAVA에서는 "우선순위 큐"라는 큐 라이브러리를 이용한다.

PriorityQueue<자료형>() = new PriorityQueue<>(); 

 

필자는 구글검색을 통해서 PriorityQueue에 대해 학습했는데,  각각의 음식을 객체로 할당하는 방식으로 구현했다.

import java.util.PriorityQueue;

class Solution {
    class food implements Comparable<food>{
        int scoville;
        food(int sco){
            scoville = sco;
        }


        @Override
        public int compareTo(food target) {
            return this.scoville >= target.scoville ? 1 : -1;
        }
    }

    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<food> priorityQueue = new PriorityQueue<>();

        for(int i =0; i< scoville.length; i++){
            priorityQueue.offer(new food(scoville[i]));
        }

        while(!priorityQueue.isEmpty()){
            if(priorityQueue.peek().scoville>=K){
                break;
            }
            if (priorityQueue.peek().scoville<K &&priorityQueue.size() == 1){
                answer = -1;
                break;
            }
            int new_food = priorityQueue.poll().scoville + priorityQueue.poll().scoville*2;
            priorityQueue.offer(new food(new_food));

            answer++;
        }
        return answer;
    }
}

food 객체에는 해당음식의 (int)스코빌지수를 나타내는 scoville값을 갖는다.

 

이런식으로 객체에 대하여 int값이 아닌 다른 값을 비교하더라도 클래스에 compareTo를 오버라이드하여,

return으로 값을 차등적으로 반환하면 된다.

 

 

코드리뷰를 살펴본 결과 PriorityQueue에 Integer값을 자료형으로 받아서 직접 비교하는 방법이 있어서 코드를 가져왔다.

import java.util.*;
class Solution {
    public int solution(int[] scoville, int K) {
        PriorityQueue<Integer> q = new PriorityQueue<>();

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

        int count = 0;
        while(q.size() > 1 && q.peek() < K){
            int weakHot = q.poll();
            int secondWeakHot = q.poll();

            int mixHot = weakHot + (secondWeakHot * 2);
            q.add(mixHot);
            count++;
        }

        if(q.size() <= 1 && q.peek() < K)
            count = -1;

        return count;
    }
}

이런식으로 Integer값으로 받게 되면 compareTo 메소드를 오버라이드하지 않아도 된다.

 

이렇게 다른 부분은 비슷한 방식으로 진행된다.

 

 

참고해야할 점은 이렇게 언제든 PriorityQueue에 값을 넣어주면 알아서 정렬이 되는 방식이다.

단, 비교해야할 값은 명확히 생성자에서 넣어주어야 한다.

 

추가적으로,

위에서 생성한 PriorityQueue를 역순으로 reverse큐를 선언하려면 아래와 같이 람다식을 이용하는 것이 좋다.

PriorityQueue<food> priorityQueue = new PriorityQueue<>();
//첫번째방법
PriorityQueue<food> reverseQueue = new PriorityQueue<>(priorityQueue.size(), 
					(food p1, food p2) -> p1.scoville >= p2.scoville ? 1 : -1);
//두번째방법
PriorityQueue<food> reverseQueue = new PriorityQueue<>(priorityQueue.size(),
			Collections.reverseOrder());
reverseQueue.addAll(priorityQueue);

혹은 두번째 방법처럼 Collections.reverseOrder() 메소드를 통해 reverse Order의 Comparator 객체를 리턴한다.

그리고 addAll을 통해서 그 뒤집은 Comparator로 비교하여 값을 집어넣는다.

 

나머지 PriorityQueue의 메소드는 Queue에서와 같다.