"명예의 전당"이라는 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 함수를 완성해주세요.
k
≤ 100score
의 길이 ≤ 1,000score[i]
≤ 2,000명예의 전당을 ArrayList 로 구현해 내림차순 정렬후 k 의 위치에 오는 가수를 삭제시켜 명예의 전당의 size 를 조절했다.
명예의 전당을 내림차순으로 정렬해 0번째 가수를 추출해 자연스럽게 가장 낮은 가수의 점수를 얻을 수 있었다.
package org.example;
import java.util.ArrayList;
import java.util.Collections;
public class Main {
public static void main(String[] args) {
int k = 3;
int[] score = {10, 100, 20, 150, 1, 100, 200};
int[] answer = new int[score.length];
//--------------------------------------//
// 명예의 전당 리스트
ArrayList<Integer> topK = new ArrayList<>();
// 명예의 전당을 계산하는 로직
for (int i = 0; i < score.length; i++) {
// 오늘의 가수의 점수를 명예의 전당에 추가
topK.add(score[i]);
// 명예의 전당 오름차순 정렬
Collections.sort(topK, Collections.reverseOrder());
// 점수가 모자라는 가수는 탈락
if (topK.size() > k) topK.remove(k);
// 명예의 전당 내림차순 정렬
Collections.sort(topK);
// 명예의 전당내의 최하위 가수의 점수를 발표점수에 입력
answer[i] = topK.get(0);
}
// answer 출력
for (int i : answer) {
System.out.println("answer = " + i);
}
}
}
PriorityQueue 를 사용해 매우 간단하게 문제를 해결했다.
이 분 말고도 대부분의 사람들이 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;
}
}
🔗 배열의 내림차순과 오름차순
🔗 PriorityQueue