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

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

프로그래머스

 

 

위의 그림은 문제의 일부분이다.

 

핵심

문제를 간단하게 해석하면, socre는 하루하루 추가되는 점수이다.

k의 개수 개까지 명예의 전당에 오르게 된다. -> 상위 k개에서 가장 낮은 점수가 커트라인이 된다.

발표 점수는 커트라인으로 이루어져 있다.

 

정답 코드,  스트림을 활용

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

class Solution {
    public  List<Integer>  solution(int k, int[] score) {
        List<Integer> scoreList = new ArrayList<>();
        List<Integer> hallOfFame = new ArrayList<>();

        for (int i =0;i<score.length;i++){
            scoreList.add(score[i]);
            
            int a = scoreList.stream()
                    .sorted(Comparator.reverseOrder())
                    .limit(k)
                    .min(Integer::compare)
                    .orElse(0);
                    
            hallOfFame.add(a);
        }

        return hallOfFame;
    }
}

해설

맨 처음 이 문제를 풀 때, 스트림을 활용하여 풀었다.

알고리즘은 간단하다. 내림차순으로 정렬하고, 우리가 원하는 크기만큼 자른다.

이후 가장 작은 값이 명예의 전당 커트가 된다.

이 값을 차례대로 리스트에 추가한다.

 

 

정답 코드, 우선순위 큐를 활용

import java.util.*;

class Solution {
    public List<Integer> solution(int k, int[] score) {
        List<Integer> hallOfFame = new ArrayList<>();
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int value : score){
            pq.offer(value);
            if(pq.size() > k){
                pq.poll();
            }

            hallOfFame.add(pq.peek());
        }
        return hallOfFame;

    }
}

해설

우선 큐는 우선순위 요소를 먼저 제거한다는 특징이 있다.

여기서 우선순위 요소는 작은 값을 의미한다.

만약 명예의 전당에 등록될 수 있는 사람의 수보다 큐에 들어간 값이 크다면,

우선순위 요소를 제거한다 -> 가장 작은 값

이후 명예의 전당에 큐에서 가장 작은 값을 넣는다.

 

 

배운 점

우선 이 문제를 처음 풀 때 우선순위 큐를 활용할 생각을 하지 못하였다.

여러 가지 풀이법을 알면 도움이 많이 될 것이라 생각되어, 둘 다 구현해보았다.

처음에 스트림을 사용하였을 때, 

min()으로 종료하고 int로 받으려고 하였더니 오류가 떴다.

이유는 타입이 잘못되었다는 것인데, 이유는 이러하다

min()이라는 최종 연산자는 null값이 나올 수도 있기 때문에 반환 타입이 Optional이다.

따라서 NullPointerException을 막기 위해 orElse()를 추가로 붙여주어야 한다.

혹은 받는 값을 Optional <Integer>로 바꾸어야 한다.