📌 문제

Lv1. 명예의 전당 (1)

"명예의 전당"이라는 TV 프로그램에서는 매일 1명의 가수가 노래를 부르고, 시청자들의 문자 투표수로 가수에게 점수를 부여합니다. 매일 출연한 가수의 점수가 지금까지 출연 가수들의 점수 중 상위 k번째 이내이면 해당 가수의 점수를 명예의 전당이라는 목록에 올려 기념합니다. 즉 프로그램 시작 이후 초기에 k일까지는 모든 출연 가수의 점수가 명예의 전당에 오르게 됩니다. k일 다음부터는 출연 가수의 점수가 기존의 명예의 전당 목록의 k번째 순위의 가수 점수보다 더 높으면, 출연 가수의 점수가 명예의 전당에 오르게 되고 기존의 k번째 순위의 점수는 명예의 전당에서 내려오게 됩니다.

이 프로그램에서는 매일 "명예의 전당"의 최하위 점수를 발표합니다. 예를 들어, k = 3이고, 7일 동안 진행된 가수의 점수가 [10, 100, 20, 150, 1, 100, 200]이라면, 명예의 전당에서 발표된 점수는 아래의 그림과 같이 [10, 10, 10, 20, 20, 100, 100]입니다.
명예의 전당 목록의 점수의 개수 k, 1일부터 마지막 날까지 출연한 가수들의 점수인 score가 주어졌을 때, 매일 발표된 명예의 전당의 최하위 점수를 return하는 solution 함수를 완성해주세요.

✔️ 제한사항

• 3 ≤ k ≤ 100
• 7 ≤ score의 길이 ≤ 1,000
  • 0 ≤ score[i] ≤ 2,000

✏️ 입출력

1. 입출력 예 #1 : 문제의 예시와 같습니다.
   
   
2. 입출력 예 #2 : 아래와 같이, [0, 0, 0, 0, 20, 40, 70, 70, 150, 300]을 return합니다.
   

💡 코드

⚠️ 런타임 에러 : 1일부터 k일까지는 무조건 명예의 전당 list 안에 들고, 이를 오름차순 정렬하여 가장 작은 값인 0번 인덱스의 값을 꺼낸다.

k일 이후에는 i일의 점수 score[i]가 list 내에서 가장 작은 점수보다 클 경우, list에서 가장 작은 0번 인덱스를 삭제하고 i일의 점수를 추가하고 이를 오름차순 정렬하여 가장 작은 0번 인덱스를 꺼낸다. i일의 점수가 0번 인덱스보다 작은 경우에는 그냥 0번 인덱스를 꺼내주면 된다.

이 풀이를 토대로 아래 코드를 작성해서 제출하였는데, 대부분 정답이였으나 9, 11번 문제에서 런타임 에러가 발생하였다!

import java.util.*;
class Solution {
    public int[] solution(int k, int[] score) {
     
        int[] answer = new int[score.length];
        List<Integer> list = new ArrayList<>();
        
        for(int i=0;i<k;i++) { // 1일 ~ k일
            list.add(score[i]);
            Collections.sort(list);
            answer[i] = list.get(0);
        }
        
        for(int i=k;i<score.length;i++) { // k일 이후
            if(score[i] > list.get(0)) {
                list.remove(0);
                list.add(score[i]);
                Collections.sort(list);
                answer[i] = list.get(0);
            } else {
                answer[i] = list.get(0);
            }
        }

        return answer;
    }
}

✅ 위 코드를 예제 창에서 실행해보니 java.lang.ArrayIndexOutOfBoundsException 에러가 발생하였다! 해당 에러는 반복 횟수가 배열의 길이보다 클 때 발생하는 에러인데, 왜 이런 에러가 발생했나 생각해보니 첫번째 for문에서 k가 score[]의 길이보다 큰 경우를 고려하지 않았던 것이였다! 즉, k = 5이면서 score.length = 3이라면 score[3], score[4]는 참조할 수 없는 범위이므로 런타임 에러가 발생하게 된다.

이를 해결하기 위해 위에서 작성했던 코드는 k가 score[]의 크기보다 작거나 같은 경우에만 실행되도록 조건을 걸었고, k가 더 큰 경우에는 반복문을 socre.length번만큼 돌도록 설정하였다.

import java.util.*;
class Solution {
    public int[] solution(int k, int[] score) {
     
        int[] answer = new int[score.length];
        List<Integer> list = new ArrayList<>();
        
        if(k <= score.length) {
            for(int i=0;i<k;i++) { // 1일 ~ k일
                list.add(score[i]);
                Collections.sort(list);
                answer[i] = list.get(0);
            }   

            for(int i=k;i<score.length;i++) { // k일 이후

                if(score[i] > list.get(0)) {
                    list.remove(0);
                    list.add(score[i]);
                    Collections.sort(list);
                    answer[i] = list.get(0);

                } else {
                    answer[i] = list.get(0);
                }
            }
        } else { // k > score.length
            for(int i=0;i<score.length;i++) {
                list.add(score[i]);
                Collections.sort(list);
                answer[i] = list.get(0);
            }
        }
        
        return answer;
    }
}

➕ 다른 사람의 코드 : PriorityQueue를 사용하여 간단하게 해결한 풀이가 있었다! 처음에 문제 풀 때 큐를 생각했었지만 정렬 문제 때문에 포기했었는데, TreeSet처럼 데이터를 입력하면 자동으로 정렬해주는 우선순위 큐가 있다는 생각을 전혀 못하고 있었다,, 기본 PriorityQueue는 오름차순 정렬을 통해 작을수록 우선 순위가 높고, Collections.reverseOrder()를 사용하면 내림차순 정렬을 수행하여 클수록 우선 순위가 높아진다.

q에 score[i]를 저장하는데, q의 크기가 k보다 커지면 poll()을 통해 q의 꼭대기값, 즉, 우선 순위가 가장 높은 제일 작은 값을 삭제한다. 그 후peek()를 통해 꼭대기값을 꺼내주면 된다.

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

       return answer;
   }
}