우선순위 큐 (Priority Queue)

큐 (Queue))

큐(Queue)는 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조입니다.
큐

우선순위 큐 (Priority Queue)

우선순위 큐(Priority Queue)는 먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조입니다. 우선순위 큐는 일반적으로 힙(Heap)을 이용하여 구현합니다.

우선순위 큐는 리스트와 연결리스트로 구현 가능합니다.

하지만 리스트의 경우 data가 많아 질 경우 데이터를 우선순위에 기반해 전체 비교를 거쳐 알맞은 자리를 찾고, 그 자리에 넣기 위해 전체 자료를 밀어내야합니다.

연결리스트의 경우 또한 data가 많아 질 경우 노드간의 연결을 거쳐 모든 노드에 접근하여 비교연산을 해야합니다. 이는 비용이 매우 크기 때문에 일반적으로 우선순위 큐는 Heap을 가지고 구현합니다.

힙 (Heap)

힙(Heap)은 우선순위 큐를 위해 고안된 완전이진트리 형태의 자료구조입니다.
여러 개의 값 중 최댓값 또는 최솟값을 찾아내는 연산이 빠릅니다.

완전이진트리?

  1. 완전 이진트리는 마지막 레벨을 제외 하고 모든 레벨이 완전히 채워져 있다.
  2. 마지막 레벨은 꽉 차 있지 않아도 되지만, 노드가 왼쪽에서 오른쪽으로 채워져야 한다.
  3. 마지막 레벨 h에서 1~2h-1 개의 노드를 가질 수 있다.
  4. 완전 이진 트리는 배열을 사용해 효율적으로 표현 가능하다.

힙의 종류는 최대 힙 과 최소 힙이 두가지가 존재합니다.

최대 힙

최대 힙이란, 부모 노드의 값 > 자식 노드의 값인 힙을 최대 힙이라고 합니다.

최소 힙

최소 힙이란 자식 노드의 값 > 부모 노드의 값인 힙을 최소 힙이라고 합니다.

힙

우선순위큐 JAVA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// Priority Queue 선언
import java.util.PriorityQueue; //import

// int형 priorityQueue 선언 (우선순위가 낮은 숫자 순) - 최소힙
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

// int형 priorityQueue 선언 (우선순위가 높은 숫자 순) - 최대힙
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

// String형 priorityQueue 선언 (우선순위가 낮은 숫자 순) - 최소힙
PriorityQueue<String> priorityQueue = new PriorityQueue<>(); 

// String형 priorityQueue 선언 (우선순위가 높은 숫자 순) - 최대힙
PriorityQueue<String> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

// 추가
priorityQueue.add(2);     // priorityQueue 값 2 추가
priorityQueue.offer(3);   // priorityQueue 값 3 추가

// 삭제
priorityQueue.poll();       // priorityQueue에 첫번째 값을 반환하고 제거 비어있다면 null
priorityQueue.remove();     // priorityQueue에 첫번째 값 제거 비어있다면 에러
priorityQueue.clear();      // priorityQueue에 초기화

// 검사
priorityQueue.peek(); // 최상단 요소 가져오기

Priority Queue API

- 예외 발생 값 리턴
추가(enquene) add(element e) offer(element e)
삭제(dequene) remove() poll()
검사(peek) element() peek()

예외발생에 있는 API는 예외를 발생하지만 값 리턴 영역에 있는 API는 true/false 값을 리턴합니다.

예시 문제

더 맵게

문제

매운 것을 좋아하는 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 합니다.

입출력 예

scoville K return
[1, 2, 3, 9, 10, 12] 7 2

답안

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import java.util.PriorityQueue;

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

        // 큐에 원소 삽입
        for(int s: scoville) {
            heap.offer(s);
        }

        while(heap.peek() <= K) {
            // scoville의 길이는 2 이상 이므로
            if(heap.size() == 1) {
                return -1;
            }

            int a = heap.poll();
            int b = heap.poll();
            
            // 최소값 2개를 scoville의 변환 후 quene에 삽입
            int result = a + (b * 2);

            heap.offer(result);
            cnt++;
        }
        return cnt;
    }
}