[알고리즘] 더 맵게 + 우선 순위 큐

코딩테스트 연습 - 더 맵게 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

-> heap(힙) 문제다 우선 순위 큐를 사용하면 쉽게 풀 수 있었다.

힙?

데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리

PriorityQueue 선언

import java.util.PriorityQueue;

//오름차순(default) PriorityQueue 선언
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

//내림차순 PriorityQueue 선언
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

메소드

add(), clear(), comparator(), contains(Object o), iterator(), offer(E e), peek(), poll(), remove(Obeject o), size(), spliterator(), toArray(), toArray(T[] a)

PriorityQueue 삽입

• add(E e)
• offer(E e)

PriorityQueue 삭제

• clear() : 모든 요소 삭제
• poll() : 헤드 요소 조회 및 삭제, 큐가 비어있을 경우 null 반환

PriorityQueue 조회

• peek() : 헤드 요소 반환, 큐가 비어있을 경우 null 반환

<코드>

public int solution(int[] scoville, int k) {
    int answer = 0;
    // 가장 작은 값을 뽑기 위해 우선순위 큐 사용
    PriorityQueue<Integer> heap = new PriorityQueue<>();

    for (int aScovile : scoville) {
        heap.offer(aScovile);
    }

    while (heap.peek() <= k) {
        // 스코빌 지수를 k이상으로 만들수 없는 경우 = 원소가 한개
        if (heap.size() == 1) {
            return -1;
        }
        // 작은 값 두개 조회
        int a = heap.poll(); // 첫번째 작은값
        int b = heap.poll(); // 두번째 작은값

        int result = a + (b*2);

        heap.offer(result); // 다시 heap에 삽입
        answer++;
    }
    return answer;
}

<수정>

while (heap.peek() < k )

문제에 모든 음식의 스코빌 지수를 k이상으로 만들수 없는 경우에는 -1을 return해준다고 했기에

아마도 테스트 케이스 18,20,21은 k랑 같은 경우였던거 같다.