[프로그래머스] 명예의 전당 (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

입출력 예

k	score	result
3	[10, 100, 20, 150, 1, 100, 200]	[10, 10, 10, 20, 20, 100, 100]
4	[0, 300, 40, 300, 20, 70, 150, 50, 500, 1000]	[0, 0, 0, 0, 20, 40, 70, 70, 150, 300]

문제 출처

https://school.programmers.co.kr/learn/courses/30/lessons/138477#

생각

• k번째 까지는 (또는 score 리스트가 k보다 작다면 score 리스트의 길이번째 까지는) 반복문을 돌면서 최솟값을 계속 업데이트. 명예의 전당 리스트는 score리스트를 복사
• k보다 클 때 부터는 명예의 전당 리스트를 업데이트
  • 명예의 전당 커트라인 점수보다 이번 회차의 점수가 더 높다면 커트라인 점수를 이번 회차 점수로 바꾼 뒤 명예의 전당 정렬

코드

import java.util.*;

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

        int min = 2000; 
        for (int i = 0; i < Math.min(k,score.length); i++) {
            if (score[i] < min) {
                min = score[i];
            }
            awardList[i] = score[i];
            answer[i] = min;
        }

        Arrays.sort(awardList);

        for (int i = k; i < score.length; i++) {
            if (score[i] > awardList[0]) {
                awardList[0] = score[i];
                Arrays.sort(awardList);
            }

            answer[i] = awardList[0];
        }

        return answer;
    }
}

다른 사람의 풀이

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

        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for(int num=0; num<score.length;num++) {
            queue.add(score[num]);
            if(queue.size()<=k) {
                answer[num]=queue.peek();
            }else {
                queue.remove();
                answer[num]=queue.peek();
            }
        }

        return answer;
    }
}

• 우선순위 큐를 이용한 풀이었다
• 커트 라인 점수를 알기 위해서는 계속 정렬을 해주어야 하는 배열과 달리, 정렬되어진 큐에서 하나씩 더하고, 제거하면 된다는 점에서 이해하기 쉬운 코드라고 생각한다😃

---

priority queue (우선순위 큐) ⭐

정의

FIFO인 큐의 구조를 가지면서, 들어온 순서대로 나가는 대신, 우선 순위가 높은 데이터가 먼저 나가는 구조를 가지는 큐

선언

import java.util.PriorityQueue;
import java.util.Collections;

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

//높은 숫자가 우선 순위인 우선순위 
PriorityQueue<Integer> priorityQueueHighest = new PriorityQueue<>(Collections.reverseOrder());

데이터 추가

priorityQueueLowest.add(10); // 큐 용량 초과 시 예외 throw
priorityQueueLowest.offer(20); // 큐 용량 초과나 크기 제한이 있는 경우  데이터 추가되지 않고 false 반환. 크기 제한이 없을 경우 요소 추가되고 `true`반환

데이터 반환 | 삭제

// 첫 원소의 값 반환 후 제거. 빈 큐일 경우 null 반환
priorityQueueLowest.poll();

// 첫 원소의 값 제거. 빈 큐일 경우 예외 throw
priorityQueueLowest.remove(); 

// 첫 원소의 값 반환만 진행. 빈 큐일 경우 null 반환
priorityQueueLowest.peek();

// 첫 원소의 값 반환만 진행. 빈 큐일 경우 예외 throw
priorityQueueLowest.element();

// 큐 초기화
priorityQueueLowest.clear();