우선순위 큐 (PriorityQueue)

코테를 풀다가 문법적인 부분에서 자꾸 막혀서 다른 분의 답을 봤는데, 우선순위 큐를 사용해서 너무 쉽게 풀어놓으셔서 정리해보았다.

-	레벨	언어	개념	정답률
문제	Lv.1	java	우선순위 큐	68%

📖 코테문제 바로가기

---

예시답변

import java.util.*;

class Solution {
    public int[] solution(int k, int[] score) {
        int[] answer = new int[score.length];

        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

        int temp = 0;

        for(int i = 0; i < score.length; i++) {

            priorityQueue.add(score[i]);
            if (priorityQueue.size() > k) {
                priorityQueue.poll();
            }

            answer[i] = priorityQueue.peek();
        }



        return answer;
    }
}

 

우선순위 큐

💡 원소들이 우선순위에 따라 정렬되어 있는 자료구조

• 일반적인 큐 : 먼저 들어온 원소가 먼저 나감
• 우선순위 큐 : 각 원소에 우선순위가 부여되어 우선순위가 높은 순서대로 원소가 나감

→ java에서는 ‘PriorityQueue’ 클래스를 사용하여 우선순위 큐를 구현함

• 기본적으로 작은 값이 우선순위가 높은 우선순위 큐로 생성됨 = 가장 작은 원소가 우선순위가 높아서 먼저 나온다는 의미!
   

예시

import java.util.PriorityQueue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        // 정수형 우선순위 큐 생성 (기본은 최소 힙)
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        // 원소 추가
        pq.add(3);
        pq.add(1);
        pq.add(4);
        pq.add(2);

        // 우선순위가 높은 순서대로 원소 출력
        while (!pq.isEmpty()) {
            System.out.println(pq.poll()); // 출력: 1, 2, 3, 4
        }
    }
}

• poll() 메서드를 통해서 우선순위가 높은 순서대로 출력됨

---

peek() 메서드

우선순위 큐에서 가장 우선순위가 높은 원소를 반환 but 큐에서 제거하지는 x
⇒ 가장 우선순위가 높은 원소를 조회

예시

import java.util.PriorityQueue;

public class PeekExample {
    public static void main(String[] args) {
        // 정수형 우선순위 큐 생성 (기본은 최소 힙)
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        // 원소 추가
        pq.add(3);
        pq.add(1);
        pq.add(4);
        pq.add(2);

        // 가장 우선순위가 높은 원소 조회 (삭제하지 않음)
        int highestPriority = pq.peek();
        System.out.println("가장 우선순위가 높은 원소: " + highestPriority); // 출력: 1

        // 여전히 큐는 원소를 가지고 있음
        System.out.println("현재 큐의 크기: " + pq.size()); // 출력: 4
    }
}

 

---

 
노션으로만 정리하다가 처음으로 개발 블로그를 벨로그에서 시작하게 되었는데, 앞으로 종종 뉴스레터나 java 개념, 혹은 안드로이드 프로젝트 관련 글들을 가져올 것 같아요...!
아직 처음이라 낯설긴하지만 다같이 열심히 개발해보자구요 🔥

🗒️ 깃허브 바로가기