[programmers] Heap - 더 맵게

 

 

import java.util.*;

//heap
public class Solution {

    public static int solution(int[] scoville, int K) {
        int answer = 0;

        //min heap
        PriorityQueue<Integer> tree = new PriorityQueue<>();

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

        Integer value = tree.poll();
        while (value < K) {
            if(tree.isEmpty())  return -1;
            tree.add(calculate(value, tree.poll()));      //계산 후 tree에 삽입
            value = tree.poll();
            answer++;
        }

        return answer;
    }

    //calculate
    private static int calculate(int min,int max) {
        return (min + (max * 2));
    }
}

Heap 자료구조를 PriorityQueue 클래스를 사용하여 구현

(PriorityQueue는 Heap을 이용하여 구현하는 것이 일반적이므로)

 

Priority Queue

- 내부 구조 : Heap, 이진트리 구조

- 비교 가능한 우선순위를 통하여 원소 삽입, 삭제됨

 

 

 

1) NoSuchElementException 주의

queue가 isEmpty() 상태일 때 remove(), element() 메소드 사용 시 예외 발생

 

-> null을 반환하는 poll(), peek() 메소드를 사용 ( NullPointerException 고려해야 함 )

 

 

++

삽입 시 생길 수 있는 예외

 

• NullPointerException : null 원소를 삽입 시
• ClassCastException : 다른 클래스 타입의 원소를 추가할 때

 

---

java.util.collections 총정리 Queue편 — 개발뿐만아니라 (tistory.com)

java.util.collections 총정리 Queue편

 

https://www.geeksforgeeks.org/priority-queue-class-in-java/

PriorityQueue in Java - GeeksforGeeks