1단계 / 138477 / 명예의전당(1)

oh_eol·2024년 1월 20일

Java 코딩테스트

Programmers

목록 보기

6/7

문제 설명

"명예의 전당"이라는 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

코드

import java.util.*;

class Solution {
    public int[] solution(int k, int[] score) {
        int[] answer = new int[score.length];
        int[] fame = new int[k];
        
        if(k > score.length) {
            for(int i = 0; i < score.length; i++){
                fame[i] = score[i];
                reverseSort(fame);
                answer[i] = fame[i];
            }
            
        } else {
            for(int i = 0; i < k; i++) {
                fame[i] = score[i];
                reverseSort(fame);
                answer[i] = fame[i];
            }
        for(int i = k; i < score.length; i++) {
            if(fame[k-1] >= score[i]) {
                answer[i] = fame[k-1];
            } else {
                fame[k-1] = score[i];
                reverseSort(fame);
                answer[i] = fame[k-1];
            }
        }
            
        }
        
        return answer;
    }

    public static void reverseSort(int[] arr) {
        Arrays.sort(arr);
        for (int i = 0; i < arr.length / 2; i++) {
            int temp = arr[i];
            arr[i] = arr[arr.length - i - 1];
            arr[arr.length - i - 1] = temp;
        }
    }
}

Error

처음에 9, 11번 테스트에서 계속 런타임 에러가 떴다.

원인

k 가 score 의길이보다 클 경우를 빠뜨린 것.

해결

해당하는 조건식으로 코드를 감싸주었다.

반성

조건식을 잘 보자! 이번 경우 각 인자들의 크기를 특히 잘 보자!

다른 사람의 풀이

PriorityQueue

PriorityQueue(우선 순위 큐)를 사용한 풀이가 많이 보였다. PriorityQueue의 특징은 다음과 같다.

높은 우선순위의 요소를 먼저 꺼내서 처리하는 구조이다.(우선순위 큐에 들어가는 원소는 비교가 가능한 기준이 있어야한다.)
내부 요소는 힙으로 구성되어 이진트리 구조로 이루어져 있다.
내부구조가 힙으로 구성되어 있기에 시간 복잡도는 O(NLogN)이다.
우선순위를 중요시해야 하는 상황에서 주로 쓰인다.

PriorityQueue의 선언은 아래와 같다.

낮은 숫자가 우선 순위인 int 형 우선순위 큐 선언
PriorityQueue priorityQueueLowest = new PriorityQueue<>();

높은 숫자가 우선 순위인 int 형 우선순위 큐 선언
PriorityQueue priorityQueueHighest = new PriorityQueue<>(Collections.reverseOrder());

PriorityQueue를 사용한 코드는 다음과 같다.

import java.util.*;

class Solution {
    public int[] solution(int k, int[] score) {
        int[] answer = new int[score.length];

        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

        int temp = 0;

        for(int i = 0; i < score.length; i++) {

            priorityQueue.add(score[i]);
            if (priorityQueue.size() > k) {
                priorityQueue.poll();
            }

            answer[i] = priorityQueue.peek();
        }



        return answer;
    }
}

이 경우, k 가 score.length 보다 큰 것이 문제가 되었던 내 풀이법과 달리 더 이상 문제될 것이 없다. 따로 fame과 같이 명예의 전당 배열을 사용하지 않고도, 우선순위가 가장 높은 수(가장 작은 수)를 반환하고 제거하지 않는 peek을 사용하기 때문이다.