[Java] 연습문제 - 명예의 전당 (1) (Lv 1)

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

프로그래머스

 

 

✔ 입출력 예

명예의 전당 입출력 예

 

 

💡 포인트

1️⃣ 매일 출연한 가수의 점수가 지금까지 출연 가수들의 점수 중 상위 K번째 이내이면 해당 가수의 점수를 명예의 전당에 올림 

👉 새로운 점수가 들어올 때마다 정렬이 필요함 = 우선순위 큐

👉 상위 K번째 이내일 때만 명예의 전당에 새로운 점수 추가

 

 

❓ 풀이 방법

1️⃣ 최하위 점수(정답)를 담을 int형 배열과 명예의 전당 리스트를 담을 우선순위 큐 선언

2️⃣ for문을 score의 길이만큼 반복

     👉 우선순위 큐(명예의 전당 리스트)의 길이가 k보다 작다면 score[i]를 추가만 함

     👉 우선순위 큐가 k 이상이고 score[i]가 pq.peek() 즉, 가장 작은 수보다 클 경우에만 pq.poll()을 하고 새로운 점수를 추가 해줌

3️⃣ 매 반복문을 실행할 때마다 answer 배열에 pq.peek() 값 담아주기

 

 

❗ 테스트 결과

👉 통과

명예의 전당 테스트 결과

 

 

✔ 소스코드

package com.likelion.programmers;

import java.util.Arrays;
import java.util.PriorityQueue;

public class Solution {  //  명예의 전당
    private int[] solution(int k, int[] score) {
        int[] answer = new int[score.length];
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for (int i = 0; i < score.length; i++) {
            if(pq.size() < k) {
                pq.offer(score[i]);
            }else if(score[i] > pq.peek()) {
                pq.poll();
                pq.offer(score[i]);
            }
            answer[i] = pq.peek();
        }

        return answer;
    }

    public static void main(String[] args) {
        Solution main = new Solution();

        int k = 3;
        int[] score = new int[]{10, 100, 20, 150, 1, 100, 200};
        System.out.println(Arrays.toString(main.solution(k, score)));
    }
}

 

우선순위 큐를 한번에 생각해냈다면 간단하게 풀 수 있었던 문제였던 것 같다.😁

이번 문제는 쉬운 문제였지만, 전에는 이런 문제를 보고도 우선순위 큐를 생각하지 못했었는데 이제는 한번에 생각해냈다는 점에서 알고리즘과 자료구조에 조금은 익숙해진 나의 성장을 확인할 수 있었던 기회였다.