프로그래머스 138477. 명예의 전당 (1) (JAVA)

1. 문제

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

2. 풀이

어쩌다 보니 계속 우선순위 큐 문제를 풀게 됐다. peek()을 알면 쉽게 풀 수 있다.

peek()은 우선순위 큐의 값을 pop 하지 않고, 맨 앞 값을 가져올 수 있다.

오름차순으로 자동 정렬되는 우선순위 큐에서는, 맨 앞 값이 최하위 점수가 된다.

 

정리하면 아래와 같은 순서로 구현했다.

 

1. 우선순위 큐와 정답을 ArrayList로 저장할 answerList 정의
2. 우선순위 큐에 k개가 다 차기 전에는 우선순위 큐에 무조건 삽입
3. peek() 함수를 통해 우선순위 큐의 맨 앞의 값을 가져와 answerList에 삽입
4. k개가 다 차면, score와 우선순위 큐의 맨 앞의 값과 비교한다.
5. 최하위 점수(맨앞 값) 보다 크면, 기존 값을 pop 하고 새로운 값을 add
6. 최하위 점수보다 작거나 같으면, 그냥 add
7. 우선순위 큐에 값이 삽입되면 peek()으로 answerList에 삽입
8. ArrayList를 stream으로 Array로 변환 후 answer 배열을 반환

3. 코드

import java.util.ArrayList;
import java.util.PriorityQueue;

class Solution {
    public int[] solution(int k, int[] score) {
       PriorityQueue<Integer> pq = new PriorityQueue<>();
        ArrayList<Integer> answerList = new ArrayList<>();
        for(int i=0;i<score.length;i++) {
            if(pq.size() == k) {
                if(pq.peek() < score[i]) {
                    pq.poll();
                    pq.add(score[i]);
                }
            } else {
                pq.add(score[i]);
            }
            answerList.add(pq.peek());
        }
        int[] answer = answerList.stream().mapToInt(i -> i).toArray();

        return answer;
    }
}