문제
"명예의 전당"이라는 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
- 0 ≤ score[i] ≤ 2,000
import java.util.LinkedList;
class Solution {
public int[] solution(int k, int[] score) {
int[] answer = new int[score.length];
int day = 0;
LinkedList<Integer> rank = new LinkedList<Integer>();
rank.add(score[0]);
answer[day++] = score[0];
for(int i = 1; i < score.length; i++) {
boolean isMin = true;
for(int j = 0; j < rank.size(); j++) {
if(score[i] >= rank.get(j)) {
rank.add(j, score[i]);
isMin = false;
break;
}
else if(j > k) { break; }
}
if(isMin) { rank.add(score[i]); }
if(rank.size() < k) {
answer[day++] = rank.get(rank.size()-1);
}
else {
answer[day++] = rank.get(k-1);
}
}
return answer;
}
}값을 하나씩 가져와 비교하면서 k번째 순위 안에 든다면 중간에 값이 삽입되어 들어가야 하므로 O(1)의 시간복잡도를 써야 한다고 생각했다. 그래서 LinkedList 를 사용했다.
값을 하나 가져와서 리스트 안의 값들과 하나씩 비교해 가면서 현재 가져온 값이 크다면 삽입 과정을 거친다.
그런데 이는 k번째 순위 밖이라면 쓸모없는 작업이므로 k번 이상 반복되면 반복문을 빠져나갔다.
그렇다면 가져왔던 값은 버리느냐, 그렇지 않다.
물론 방법에 따라서 버려도 되는 상황이 있을 수 있지만, 나는 맨 뒤에다 값을 추가하는 방법을 택했다.
왜냐하면 k번째 이상 반복이 되었다면, 문제에서 말하는 명예의 전당의 수는 이미 차있는 상태이다. 그런데 k번째 이하라면 값을 삽입하는 조건에 해당하지 못했다 하더라도 맨 뒤에 값을 추가해야 이후 가져오는 값들에 대해서도 연산이 가능해질 것이라 생각했다.
그리고 왠지 k번째 이하는 일단 무조건 명예의 전당에 들어선다는 조건을 따로 또 만들어야 하나 싶었던 이유도 있었다.
다른 사람들은 어떻게 풀었나 싶었는데, 우선순위 큐를 다들 사용했었다.
우선순위 큐, 이론만 들었을 뿐 한 번도 사용해 본 적이 없던 터라 전혀 생각도 못했었다.
우선순위를 정하고 이진트리로 구성하는데 어떻게 여기서 명예의 전당을 걸러내나 싶었는데, 아래 코드를 가지고 이미지를 그려보니 단번에 이해가 되었다.
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;
}
}poll을 하면서 우선순위가 높은 값을 꺼내오다 보니 자연스럽게 peek 하면서 명예의 전당 수에 들어있는 값 중 최솟값을 가져오는 것을 알 수 있었다.
다음번에 꼭 써먹어봐야겠다.
출처
https://school.programmers.co.kr/learn/courses/30/lessons/138477