[Programmers] [JAVA] 더 맵게

https://programmers.co.kr/learn/courses/30/lessons/42626

코딩테스트 연습 - 더 맵게

 

package com.company.practice.programmers;

import java.util.*;

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

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

        while (heap.peek() < K) {
            if (heap.size() < 2) return -1;
            int f1 = heap.poll();
            int f2 = heap.poll();

            int newFood = f1 + (f2 * 2);
            heap.offer(newFood);
            answer++;
        }

        return answer;
    }
}

 

heap을 사용하여 가장 작은 두개를 더해준다. 이 과정을 반복하여 답을 구한다.

자바에서 제공하는 heap은 poll과 peek을 함께 제공하여 작은값을 찾는 과정을 거치지 않아도 자동으로 가장 작은 값을 가져온다. 이 과정으로 정렬이나 최솟값을 구하는 반복 작업을 없앨 수 있다.

 

---

이론 - Heap

 

Heap이란 완전 이진 트리의 종류로, 우선순위 큐를 구현하기 위해 만들어진 자료구조이다. 여러 값 중 최대 또는 최솟값을 찾기에 가장 적합한 자료구조이다. 따라서 최대 힙과 최소 힙으로 구분하며 최대 힙은 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리이며, 반대로 최소 힙은 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리이다.

힙을 구현하는 기본적인 자료구조는 배열이다. 인덱스를 통해 노드를 찾아서 계산한다. 힙에 새로운 요소가 들어오면, 마지막 노드 다음에 삽입한다. 이후 힙의 성질을 이용한 교환 작업으로 다시 힙을 만들어준다. 힙에서 노드를 삭제할 때는 루트 노드 (최상위 노드)를 삭제한다. 삭제 후에는 힙의 가장 마지막 노드를 루트로 가져오고, 힙의 성질을 이용하여 재배열한다. 

 

Heap - Java에서의 사용

자바에서는 힙을 구현할 때 우선순위 큐 (Priority Queue)를 사용한다. 일반적인 FIFO 방식과는 다르게 우선순위를 먼저 결정하고, 최우선순위의 원소가 나가는 자료구조이다. 자바에서 Priority Queue를 사용하기 위해서는 라이브러리 java.util.PriorityQueue를 이용한다. 

 

선언

//우선순위가 낮은 숫자 순
PriorityQueue<Object> priorityQueue = new PriorityQueue<>();
//우선순위가 높은 숫자 순
PriorityQueue<Object> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

 

큐에 값 삽입

// value 삽입
priorityQueue.add(value);
priorityQueue.offer(value);

add는 Collection에서, offer은 Queue에서 나온 기능이다.

add는 삽입에 성공 시 true를 반환하고, 실패 시 IllegalStateException을 발생시킨다. 값을 추가하면 자동으로 정렬이 이루어진다. 

offer은 실패 시 false를 반환한다.

 

큐에 값 삭제

//첫번째 값 반환, 비어있다면 null 반환
priorityQueue.poll();
//첫번째 값 제거
priorityQueue.remove();
//큐 초기화
priorityQueue.clear();

poll 이나 remove를 사용하여 원소를 제거한다. poll은 큐가 비어있다면 null 을 반환한다.

 

우선순위가 가장 높은 값 구하기

//큐의 첫번째 값 참조
priorityQueue.peek();