프로그래머스 명예의 전당(1), PriorityQueue

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

 

문제를 보니 딱 봐도 내가 모르는 컬렉션 프레임워크(자료 구조) 써먹어서 풀라는 것 같다.

뻘짓 2시간 뒤 오름차 순으로 정렬된 queue가 존재한다면 풀기 쉬울 것 같아서 찾아보니 PriorityQueue라는게 존재한다.

 

PriorityQueue

우선순위 큐를 구현한 것이다.

요소들이 우선순위에 따라 정렬되는 특수한 형태의 큐이다.

이 큐는 최소 힙(min heap)을 사용하여 요소들을 내부적으로 관리한다.

 

특징

1. 자동 정렬
   • 요소들이 추가될 때마다 자동으로 정렬된다. 기본적으로 요소들은 오름차순으로 정렬되나, 커스텀 비교자를 사용하여 사용자 정의 순서로 정렬할 수도 있다.
     • 커스텀 비교자 예시

     • // 내림차순으로 정렬하기 위한 커스텀 비교자
       Comparator<Integer> customComparator = (a, b) -> b - a;
       
       // 커스텀 비교자를 사용하여 PriorityQueue 생성
       PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(customComparator);

2. 빠른 접근
   • 큐에서 우선순위가 가장 높은 요소(기본은 오름차순)을 빠르게 접근할 수 있다
3. Null 값을 허용하지 않음
4. 비동기적
   • 동기화를 지원하지 않으므로, 멀티스레드 환경에서는 PriorityBlockIngQueue를 사용한다.

주요 메서드들은 Queue에 존재하는 메서드와 같다.

 

 

 

 

 

 

 

 

내가 짠 코드

import java.util.*;

class Solution {
    public int[] solution(int k, int[] score) {
        int[] answer = new int[score.length];
        PriorityQueue<Integer> list = new PriorityQueue<>();
        
        for(int i = 0; i < score.length; i++){
            list.add(score[i]);
            
            if(list.size() > k){ //Queue가 명예의 전당의 크기보다 커지면
                list.poll(); // 제일 작은거 방출
            }
            
            answer[i] = list.peek(); //제일 작은 값 리턴 받아서 answer에 대입
        }
        return answer;
    }
}