[프로그래머스/Lv.1] 명예의 전당 (1)

"명예의 전당"이라는 TV 프로그램에서는 매일 1명의 가수가 노래를 부르고, 시청자들의 문자 투표수로 가수에게 점수를 부여한다. 매일 출연한 가수의 점수가 지금까지 출연 가수들의 점수 중 상위 k번째 이내이면 해당 가수의 점수를 명예의 전당이라는 목록에 올려 기념한다.

즉 프로그램 시작 이후 초기에 k일까지는 모든 출연 가수의 점수가 명예의 전당에 오르게 된다. k일 다음부터는 출연 가수의 점수가 기존의 명예의 전당 목록의 k번째 순위의 가수 점수보다 더 높으면, 출연 가수의 점수가 명예의 전당에 오르게 되고 기존의 k번째 순위의 점수는 명예의 전당에서 내려오게 된다.

 

1. Input, Output, Example

- 명예의 전당 목록의 점수의 개수 k, 1일부터 마지막 날까지 출연한 가수들의 점수인 score가 주어졌을 때, 매일 발표된 명예의 전당의 최하위 점수를 담은 배열을 반환

 

2. Constraint

1) 3 ≤ k ≤ 100

2) 7 ≤ score의 길이 ≤ 1,000

3) 0 ≤ score[i] ≤ 2,000

 

3. Code

import java.util.*;
class Solution {
    public int[] solution(int k, int[] score) {
        int[] ans = new int[score.length];
        int[] honor = new int[k]; // 뒤로 갈수록 높은 점수
        for(int i=0 ; i<score.length ; i++){
            insert(honor, score[i]);
            if(i<k) ans[i] = honor[k-1-i];
            else ans[i] = honor[0];
        }
        return ans;
    }
    
    static void insert(int[] arr, int x){
        for(int i=arr.length-1 ; i>=0 ; i--){
            if(arr[i]<=x){
                for(int j=0 ; j<i ; j++)
                    arr[j] = arr[j+1];
                arr[i] = x;
                break;
            }
        }
    }
}

- +1