자바 - PriorityQueue로 코테 푸는 법

두둥 😄 두둥 🥹 지나친 학습으로 인해 미쳐 가고 있다. 🤪

 

1. 그래서, 언제 PriorityQueue를 써야 되나요?

 

프라이어리티 큐(Priority Queue)는 특정 기준에 따라 우선 순위를 부여하여 가장 우선 순위가 높은 요소를 먼저 처리하는 자료구조입니다. 코딩 테스트에서 다음과 같은 유형의 문제를 해결할 때 프라이어리티 큐를 유용하게 사용할 수 있습니다:

1. 최소 또는 최대 요소 찾기: 요소들 중 최소값 또는 최대값을 빠르게 찾아내야 할 때, 특히 반복적으로 최소값 또는 최대값을 추출해야 하는 경우에 프라이어리티 큐를 사용합니다. <- 오!!!
2. 다익스트라 알고리즘: 최단 경로를 찾는 알고리즘 중 하나로, 각 정점까지의 최단 거리를 계산할 때 우선 순위 큐를 사용하여 현재 가장 짧은 거리를 가진 정점을 빠르게 선택합니다. <- 데이크스트라 써야 된다면 프라이어리티큐 쓰자!!!
3. 허프만 코딩: 허프만 코딩 트리를 생성할 때 사용되는 알고리즘으로, 가장 낮은 빈도수를 가진 노드들을 우선 순위 큐에서 빠르게 선택하여 새로운 노드를 만들고 다시 큐에 삽입하는 과정을 반복합니다.
4. 이벤트 시뮬레이션: 특정 이벤트나 작업에 대해 시간 순서대로 처리해야 할 때, 예를 들어 시뮬레이션 게임이나 이벤트 기반 시스템에서 각 이벤트의 발생 시간을 기준으로 우선 순위를 부여하여 처리합니다.
5. 프림 알고리즘: 최소 신장 트리를 찾는 데 사용되는 알고리즘으로, 연결된 간선들 중 가장 낮은 가중치를 가진 간선을 선택하는 데 우선 순위 큐를 사용합니다.
6. 크루스칼 알고리즘: 이 알고리즘도 최소 신장 트리를 찾는데 사용되며, 간선의 가중치를 기준으로 우선 순위 큐를 통해 가장 작은 가중치를 가진 간선부터 처리할 수 있습니다.
7. 그리디 알고리즘 문제: 특정 조건을 만족하는 요소를 선택할 때 우선 순위 큐를 이용하여 그리디(greedy) 선택을 수행할 수 있습니다.

이러한 유형의 문제들에서 프라이어리티 큐를 사용하면, 효율적으로 문제를 해결할 수 있는 방법을 제공하여, 실행 시간을 크게 줄일 수 있습니다.

 

1, 2, 7 외에는 잘 모른다. 🥲 빨리 저 내용까지 포스팅 할 수 있도록 공부하겠다...!

 

2. 프라이어리티큐로 푸는 문제와 답을 봅시다! 

 

PriorityQueue를 활용한 코딩 테스트 문제 중 대표적인 것은 "K번째 가장 큰 요소 찾기" 문제입니다. 이 문제는 우선순위 큐를 활용하여 효율적으로 해결할 수 있으며, PriorityQueue의 특성을 잘 이해하고 사용해야 하는 문제입니다.

문제: K번째 가장 큰 요소 찾기

문제 설명: 정수 배열 nums와 정수 k가 주어질 때, 배열에서 k번째로 큰 요소를 반환합니다.

 

예시:

• 입력: nums = [3,2,1,5,6,4], k = 2
• 출력: 5
• 설명: 배열을 정렬하면 [1,2,3,4,5,6]이 되며, 여기서 두 번째로 큰 요소는 5입니다.

최적의 솔루션

import java.util.PriorityQueue;

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        // 최소 힙을 사용하는 우선순위 큐를 생성합니다.
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        // 모든 배열 요소를 순회하며 큐에 추가합니다.
        for (int num : nums) {
            pq.offer(num);
            // 큐의 크기가 k를 초과하면, 가장 작은 요소(큐의 헤드)를 제거합니다.
            if (pq.size() > k) {
                pq.poll();
            }
        }
        
        // 큐의 헤드에는 k번째로 큰 요소가 남습니다.
        return pq.peek();
    }
}