[프로그래머스 / Java] 명예의 전당

 

📍 생각대로 코딩

• k일 까지는 그냥 낮은 값이 발표 점수이고
• k일 이후부터는 배열정렬해서 찾으면 되지않을까
• k가 score 배열의 길이보다 클 때와 작을 때도 있으니 그것도 체크

import java.util.Arrays;
class Solution {
    public int[] solution(int k, int[] score) {
        int[] answer = new int[score.length];
        
        // 명예의 전당 배열 설정
        // 초기값 설정
        
        int[] arr = new int[k+1];
        int min = score[0];
        arr[0] = min;
        answer[0] = min;
        
        if(k<score.length) {
            // k일까지는 배열에 값 삽입 
            // 기존 발표점수보다 낮다면 이 점수가 발표점수
            
            for(int i=1; i<k; i++) {
                arr[i] = score[i];
                if(min>score[i]) {
                    min = score[i];
                }
                answer[i] = min;
            }
            Arrays.sort(arr);

            // k일 이후부터는 값 삽입 후 정렬
            // 배열의 첫번째 값이 아닌 두번째 수
            // (초기 arr 배열의 크기를 k+1로 한 이유)
            
            for(int i=k; i<score.length; i++) {
                arr[0] = score[i];
                Arrays.sort(arr);
                answer[i] = arr[1];
            }
        } else {
            for(int i=1; i<score.length; i++) {
                arr[i] = score[i];
                if(min>score[i]) {
                    min = score[i];
                }
                answer[i] = min;
            }
        }
        
        return answer;
    }
}

 

📍 우선순위 큐(Priority Queue)

이 문제의 핵심은 데이터들이 삽입되고 우선순위를 정해 내보내는 것으로 우선순위 큐를 이용하여 쉽게 해결할 수 있다

import java.util.PriorityQueue;
class Solution {
    public int[] solution(int k, int[] score) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        int[] answer = new int[score.length];
        for(int i = 0; i < score.length; i++){
            if(i < k){
                queue.add(score[i]);
                answer[i] = queue.peek();
            }else{
                queue.add(score[i]);
                queue.poll();
                answer[i] = queue.peek();
            }
        }
        return answer;
    }
}

1. PriorityQueue queue = new PriorityQueue<>();
   -> int형 priorityQueue 선언 (우선순위가 낮은 숫자 순)
2. k일까지는 모든 출연 가수의 점수가 명예의 전당에 오르고 아래 그림과 같은 과정으로 정렬된다.

1. Priority Queue에서 우선순위가 가장 높은 값을 참조하고 싶다면 peek()라는 메서드를 활용하면 된다.
   k일 까지는 peek()을 이용하면 우선순위가 가장 낮은 즉, 가장 작은 수가 출력된다.
2. k일 이후는 삽입 후 정렬 그 후 첫번째 값을 제거해야한다. priorityQueue에서 poll()이라는 메서드를 활용하면 첫번째 값을 반환하고 제거한다.
3. 그 후 똑같이 peak() 메서드를 활용하면 가장 낮은 수가 출력된다.