[Programmers/JAVA] Lv.1 명예의 전당(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

---

INPUT & OUTPUT

/**
 * @param {int} k
 * @param {int[]} number
 * @return {int[]}
 */

---

STRATEGY_SOLUTION1

1. score -> List로 생성
2. List 정렬
3. answer 뒤에서부터 채우기
   • 순차적으로 점수를 추가하지 않고 역순으로 점수 제거하기 때문
4. List의 k순위 인덱스 = List.size() - k
   • 인원이 k보다 작다면 0 인덱스가 최하위
5. score 마지막 인덱스부터 List에서 remove()

⚠️CAUTION

• List가 오름차순이기 때문에 k 순위 주의

---

SOLUTION1

import java.util.List;
import java.util.ArrayList;
import java.util.Collections;

class Solution1 {
    public int[] solution(int k, int[] score) {
        List<Integer> list = new ArrayList<>();
        for (int s : score) {
            list.add(s);
        }
        Collections.sort(list);
        int[] answer = new int[score.length];
        for (int i = score.length - 1; i >= 0; i--) {
            if (list.size() > k) {
                answer[i] = list.get(list.size() - k);
            } else {
                answer[i] = list.get(0);
            }
            list.remove(list.indexOf(score[i]));
        }
        return answer;
    }
}

---

STRATGY_SOLUTION2

1. k 순위까지만 관리
2. k 순위보다 사람이 많아지면 최하위 점수 제거

⚠️CAUTION

• PriorityQueue
  • 높은 우선순위의 요소를 먼저 꺼내서 처리하는 구조

---

SOLUTION2

import java.util.PriorityQueue;

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

        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        for (int i = 0; i < score.length; i++) {
            priorityQueue.add(score[i]);
            if (priorityQueue.size() > k) {
                priorityQueue.poll();
            }
            answer[i] = priorityQueue.peek();
        }
        return answer;
    }
}

---

REMIND

• PriorityQueue 값 추가하기: add(), offer()
• PriorityQueue 값 삭제하기
  • poll() : priorityQueue에 첫번째 값을 반환하고 제거 비어있다면 null
  • remove() : priorityQueue에 첫번째 값 제거
  • clear() : priorityQueue에 초기화
• PriorityQueue에서 우선순위가 가장 높은 값 출력
  • peek() : priorityQueue에 첫번째 값 참조