[프로그래머스] 명예의 전당 (1)

fsm12·2023년 6월 21일

프로그래머스

목록 보기

16/57

문제링크

문제 이해

[ 입력형태 / 조건 ]

k
명예의 전당 목록의 점수의 개수 | 3

score
1일부터 마지막 날까지 출연한 가수들의 점수 | [10, 100, 20, 150, 1, 100, 200]

[ 문제 ]

=> 명예의 전당에 상위 k개의 점수가 올라갈 때, 매일 발표된 명예의 전당의 최하위 점수를 return

[ 풀이 ]

우선순위 큐에 점수를 넣어두고 peek()한 결과보다 score 배열의 값이 크다면 poll() 후 add() 연산

코드

> [성공] 1차 시도 : PriorityQueue 이용

생각한 풀이 그대로 구현

import java.util.*;

class Solution {
    public int[] solution(int k, int[] score) {
        int score_len = score.length;
        int[] answer = new int[score_len];
        int ans_idx = 0;
        
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        if(score_len < k){
            k = score_len;
        }
        
        for(int i=0; i<k; i++){
            pq.add(score[i]);
            answer[ans_idx++] = pq.peek();
        }
        
        for(int i=k; i<score_len; i++){
            if(pq.peek() < score[i]){
               pq.poll();
               pq.add(score[i]);
            } 
            answer[ans_idx++] = pq.peek();
        }
        return answer;
    }
}

=> 주의점) k가 score배열의 크기보다 클 수 있으므로 예외처리를 해주어야 함

> [성공] 2차 시도 : PriorityQueue 이용 + 1차 시도 코드 줄이기

import java.util.*;

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

        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int sc : score){
            pq.add(sc);
            if(pq.size() > k){
                pq.poll();
            }
            answer[ans_idx++] = pq.peek();
        }
        return answer;
    }
}

=> 주의점) 예외 처리코드를 굳이 쓰지 않아도 잘 동작하였지만, 오히려 처음보다 느렸음.
pq.size()에서 많은 시간을 썼을거라 생각했음

> [성공] 3차 시도 : PriorityQueue 이용 + pq.size() 개선

import java.util.*;

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

        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int sc : score){
            pq.add(sc);
            pq_size += 1;
            if(pq_size > k){
                pq.poll();
                pq_size -= 1;
            }
            answer[ans_idx++] = pq.peek();
        }
        return answer;
    }
}