[JAVA]더 맵게 + Priority Queue

힙(Heap Tree)

완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.
여러 개의 값 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 이진 트리

일종의 반정렬 상태(느슨한 정렬 상태) 를 유지
큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도
즉, 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리
힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.)
완전 이진트리(마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있는 트리의 형태)를 기본으로 하고 있고, 그 목적에 맞게 두 개의 타입으로 나뉜다.

1. Max-heap

• 루트 노드의 key는 무조건 해당 노드의 자식 노드들의 key보다 크거나 같다. 
• 같은 속성이 모든 sub-tree들에게도 재귀적으로 적용된다.

2. Min-heap

• root 노드의 키값이 모든 자식들의 키 보다 작거나 같다.
• 재귀적으로 자식 트리들 하나하나 모두 해당 조건을 만족한다.

 

Priority Queue

우선순위 큐, 일반적인 큐의 구조(FIFO)를 가지면서, 데이터가 들어온 순서대로 데이터가 나가는 것이 아닌 우선순위를 먼저 결정하고, 그 우선순위가 높은 데이터가 먼저 나가는 자료 구조

 

• PriorityQueue를 사용하기 위해서는 우선순위 큐에 저장할 객체는 필수적으로 Comparable Interface를 구현해야 한다.
• Comparable Interface를 구현하면, compare To 메서드를 override 하게 되고 해당 객체에서 처리할 우선순위 조건을 리턴해주면, PriorityQueue가 알아서 우선순위가 높은 객체를 추출해준다.
• PriorityQueue는 Heap을 이용해 구현하는 것이 일반적
• 데이터를 삽입 할 때 우선순위를 기준으로 최대 힙 혹은 최소 힙을 구성하고, 데이터를 꺼낼 때 루트 노드를 얻어낸 뒤 루트 노드를 삭제할 때는 빈 루트 노드 위치에 맨 마지막 노드를 삽입한 후 아래로 내려가면서 적절한 자리를 찾아 옮기는 방식으로 진행된다. 
• 최대 값이 우선순위인 큐 = 최대 힙, 최소 값이 우선순위인 큐 = 최소 힙

높은 우선순위의 요소를 먼저 꺼내서 처리하는 구조(기준이 있어야 한다.)	내부 요소는 힙으로 구성되어 이진트리 구조로 이루어져 있음
내부구조가 힙으로 구성되어 있어 시간복잡도 O(NLogN)	우선순위를 중요시해야 하는 상황에서 주로 쓰임

priorityQueue의 선언

import java.util.PriorityQueue;
import java.util.Collections;

//낮은 숫자가 우선 순위인 int 형 우선순위 큐 선언
PriorityQueue<Integer> priorityQueueLowest = new PriorityQueue<>();

//높은 숫자가 우선 순위인 int 형 우선순위 큐 선언
PriorityQueue<Integer> priorityQueueHighest = new PriorityQueue<>(Collections.reverseOrder());

 

• priorityQueue의 삽입과 제거는 일반 Queue의 삽입과 제거랑 동일!(add, offer) 
  • add() 메서드는 Collection클래스에서 가져오는 메서드라면, offer() Queue클래스에서 가져오는 메서드

// 첫번째 값을 반환하고 제거 비어있다면 null
priorityQueueLowest.poll();

// 첫번째 값 제거 비어있다면 예외 발생
priorityQueueLowest.remove(); 
remove(int Index) 메서드를 사용하면 Index 순위에 해당하는 값을 제거


// 첫번째 값을 반환만 하고 제거 하지는 않는다.
// 큐가 비어있다면 null을 반환
priorityQueueLowest.peek();

// 첫번째 값을 반환만 하고 제거 하지는 않는다.
// 큐가 비어있다면 예외 발생
priorityQueueLowest.element();

// 초기화
priorityQueueLowest.clear();

---

문제 설명

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

제한 사항

• scoville의 길이는 2 이상 1,000,000 이하입니다.
• K는 0 이상 1,000,000,000 이하입니다.
• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

입출력 예scovilleKreturn

[1, 2, 3, 9, 10, 12]

7

2

입출력 예 설명

1. 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
   가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]
2. 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
   가진 음식의 스코빌 지수 = [13, 9, 10, 12]

모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.

---

[풀이 방법]

1. 낮은 숫자가 우선인 int 형 우선순위 큐 선언(스코빌 지수가 가장 낮은 두 개의 음식을 섞어야 하기 때문!)
2. 큐 안에 scoville 넣는다. 
3. heap에서 제일 처음 원소가 K보다 작을 때만 while문을 돌린다.
   
   1. 큐 에서 첫 번째와 두 번째를 빼내서 섞은 다음에
   2. 섞은 것을 큐에 넣는다. 
      1. 넣을 때는 큐에 특징에 의해 넣어지게 된다. 
      2. 그때 answer ++
      3. scoville의 길이는 2 이상이기 때문에 2보다 작게된다면 -1 return

넣어질 때의 예시
[1, 2, 3, 9, 10, 12] => 1, 2가 빠지고 5를 추가한다.
[3, 5, 10, 12, 9] => 3, 5가 빠지고 13을 추가한다.
[9, 10, 12, 13]

 

import java.util.*;

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

        for (int i : scoville)  heap.offer(i);
        
        while (heap.peek() < K) {
            if (heap.size() < 2) return -1;
            int weakHot = heap.poll();
            int secondWeakHot = heap.poll();
            int mix = weakHot + secondWeakHot * 2;
            heap.offer(mix);
            answer ++;
        }
        return answer;
    }
}

 

• 트리구조 아직 어렵다.. 이론 상으로 알겠는데 이게 적용되는게 어려운 것 같다..! 힙이나 priorityQueue 알게되는 게 더 있으면 더 추가할 예정!

---

우선순위 큐

우선순위 큐 개념 사용법 정리