이중 우선순위 큐 - Heap - 프로그래머스 - Java

https://school.programmers.co.kr/learn/courses/30/lessons/42628

프로그래머스

 

1. Heap

힙은 완전 이진 트리를 기반으로 한 자료구조로, 최댓값 또는 최솟값을 빠르게 찾아내는 데 유용하다.

 

힙의 주요 특징

• 완전 이진 트리
• 부모 노드와 자식 노드 간에 특정한 순서가 있다.
• 중복된 값을 허용한다.
• 형제 노드 간에는 순서가 정해지지 않는다.

 

2. Max Heap과 Min Heap의 차이

2 - 1. Max Heap(최대 힙)

부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같다.

루트 노드에 최댓값이 위치한다.

 

2 - 2. Min Heap(최소 힙)

부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같다.

루트 노드에 최솟값이 위치한다.

 

3. Heap 사용 예시

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

public class HeapExample {
    public static void main(String[] args) {
        // 최소 힙 생성
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        // 최대 힙 생성
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

        // 요소 추가
        minHeap.offer(5);
        minHeap.offer(2);
        minHeap.offer(8);
        minHeap.offer(1);

        maxHeap.offer(5);
        maxHeap.offer(2);
        maxHeap.offer(8);
        maxHeap.offer(1);

        // 요소 출력
        System.out.println("최소 힙:");
        while (!minHeap.isEmpty()) {
            System.out.println(minHeap.poll());
        }

        System.out.println("\n최대 힙:");
        while (!maxHeap.isEmpty()) {
            System.out.println(maxHeap.poll());
        }
    }
}

최소 힙:

1

2

5

8

 

최대 힙:

8

5

2

1

 

4. 주요 메서드

• offer(): 요소 추가
• poll(): 최상위 요소 제거 및 반환
• peek(): 최상위 요소 조회(제거하지 않음)
• isEmpty(): 큐가 비어있는지 확인
• remove(): 파라미터로 넘겨진 값 제거

 

5. 이중 우선순위 큐 - 프로그래머스 문제 풀이

https://school.programmers.co.kr/learn/courses/30/lessons/42628

프로그래머스

 

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

/**
 * 241121 목 - 보너스 문제
 * 이중 우선순위 큐 - 힙
 * https://school.programmers.co.kr/learn/courses/30/lessons/42628
 * */
public class DualPriorityQueue {

    public int[] solution(String[] operations) {
        int[] answer = new int[2];
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        for (String operation : operations) {
            String[] split = operation.split(" ");
            int num;

            switch (split[0]) {
                case "I" -> {
                    num = Integer.parseInt(split[1]);
                    minHeap.add(num);
                    maxHeap.add(num);
                }
                case "D" -> {
                    if (minHeap.isEmpty()) continue;

                    if (split[1].equals("1")) {
                        num = maxHeap.poll();
                        minHeap.remove(num);
                    } else {
                        num = minHeap.poll();
                        maxHeap.remove(num);
                    }
                }
            }
        }

        if (minHeap.isEmpty()) {
            return new int[]{0, 0};
        }

        return new int[]{maxHeap.peek(), minHeap.peek()};
    }

    public static void main(String[] args) {
        DualPriorityQueue dq = new DualPriorityQueue();
        // 테스트 케이스 1
        String[] operations1 = {"I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1"};
        int[] result1 = dq.solution(operations1);
        System.out.println("Test Case 1: [" + result1[0] + ", " + result1[1] + "]");

        // 테스트 케이스 2
        String[] operations2 = {"I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "D -1", "I 333"};
        int[] result2 = dq.solution(operations2);
        System.out.println("Test Case 2: [" + result2[0] + ", " + result2[1] + "]");
    }
}

 

References

https://go-coding.tistory.com/25

https://innovation123.tistory.com/111