프로그래머스 명예의전당 - 자바(java) 우선순위 큐

명예의 전~당

 

일단 문제를 읽어보면 점수가 담긴 배열과, 명예의 전당 k가 주어진다.

k는 금 은 동메달처럼 점수가 높은 사람들의 숫자이다.

result에는 그 중 최솟값을 넣어서 일차별로 출력하면 되는 문제이다.

간단하게 느껴서 작성했다.

 

import java.util.*;
class Solution {
    public int[] solution(int k, int[] score) {
        int[] answer = new int[score.length];
        int[] annor = new int[k];
        int min = 2001;                    // 0~2000 이므로 최소값을 위한 값.
        
        for(int i = 0; i < k; i++){        // k까지는 입력 후 최소값 = 발표점수
            annor[i] = score[i];
            if(min > score[i])
                min = score[i];
            answer[i] = min;
        }Arrays.sort(annor);               // 배열 정리.
        
        for(int i = k; i < score.length; i++){
            if(annor[0] > score[i]){       // 배열의 0번째 = 명예의 전당의 최소값.
                answer[i] = annor[0];      // 최소값보다 작다면 기존 최소값 출력.
            }else if(annor[0] <= score[i]) // 최소값보다 크다면
                annor[0] = score[i];       // 값을 넣고
                Arrays.sort(annor);        // 정렬
                answer[i] = annor[0];
        }
        
        return answer;
    }
} 

 

정렬의 시간복잡도 때문에,,

이게 웬걸.. 포문에 정렬까지 들어가니 런타임에러가 불가피했다.

Arrays.sort()는 내부적으로 DualPivotQuicksort.sort()를 호출해서 사용하므로 퀵 정렬을 따라간다.

퀵 정렬의 시간 복잡도는 최선의 경우에는 O(nlogn), 최악의 경우에는 O(n^2)이다.

 

어떻게 하면 런타임 에러를 피할까 고민했는데,  방법을 못 찾았고 다른 알고리즘을 찾아보게 되었다.

 

import java.util.*;
class Solution {
    public int[] solution(int k, int[] score) {
        int[] answer = new int[score.length];
        ArrayList<Integer> annor = new ArrayList<>();
        int min = 2001;
        
        for(int i = 0; i < k; i++){       
            annor.add(score[i]);
            if(min > score[i])
                min = score[i];
            answer[i] = min;
        }Collections.sort(annor);  
 
        for(int i=k; i<score.length; i++) {
            annor.add(score[i]);
            Collections.sort(annor);
            annor.remove(0);
            answer[i] = annor.get(0);
        }              
        return answer;
    }
}
                
 

리스트 정렬에 사용되는 Collections.sort() 는 최악도 n log n이라 사용했는데,, 이것도 런타임 오류가 발생했다.

 

아무래도 반복적으로 정렬을 해야 해서 런타임오류가 발생하는데

다른 분이 우선순위 큐로 푸신 게 있어서 확인해 보았다.

 

import java.util.*; class Solution { public static int[] solution(int k, int[] score) { int[] answer = new int[score.length]; PriorityQueue annor = new PriorityQueue<>(); // 낮은 숫자가 우선 순위. 반대로하려면 Collections.reverseOrder() 추가작성. for (int i = 0; i < score.length; i++) { annor.offer(score[i]); // add, offer로 추가 if (annor.size() > k) { // 우선순위 큐 개수 > k 경우 annor.remove(); // remove를 통해 제거. } answer[i] = annor.peek(); // 우선순위 높은 값 출력, } return answer; } }

2/3 정도 단축!

왜 이렇게 빠른가 하니 일반 큐와 다르게 우선순위를 결정하고, 우선순위가 높으면 먼저 나가는 구조라서 지금 문제에 적합한 알고리즘이었다. 힙으로 구성되어 이진트리 구조이므로 O(NLogN)이다.

 

연산방식은 그림으로 표현 잘해주신 게 있어서 가져와씀다.

그림 출처:https://coding-factory.tistory.com/603

그림 출처:https://coding-factory.tistory.com/603