(Java)프로그래머스 - 명예의 전당(1)

나의 풀이

import java.util.*;

class Solution {
    public int[] solution(int k, int[] score) {
        int[] answer = new int[score.length];
        ArrayList<Integer> list = new ArrayList<>(); // 1
        
        for (int i = 0; i < score.length; i++) {
            if (i < k) { // 2
                list.add(score[i]);
                Collections.sort(list, Collections.reverseOrder());
                answer[i] = list.get(i);
            } else { // 3
                if (score[i] > list.get(k - 1)) {
                    list.set(k - 1, score[i]);
                    Collections.sort(list, Collections.reverseOrder());
                }
                answer[i] = list.get(k - 1); // 4
                if (list.size() > k) { // 5
                    list.remove(k);
                }
            }
        }
        
        return answer;
    }
}

과정

1. 명예의 전당 list를 만들어준다
2. 만약 i(일차)가 k(명예의 전당)보다 작다면 score[i]를 list에 넣어주고 list를 내림차순으로 정렬 후 answer에 list의 가장 작은 값을 넣어준다
3. 만약 i가 k보다 크고 score[i]가 list의 마지막 요소보다 크다면 list의 마지막 요소를 score[i]로 바꿔주고, 다시 내림차순 정렬한다
4. 정렬된 list의 최솟값을 answer[i]번째에 넣는다
5. 만약 list의 크기가 k보다 커지면 list의 마지막 요소를 삭제한다

다른 사람 풀이

import java.util.*;

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

        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

        int temp = 0;

        for(int i = 0; i < score.length; i++) {

            priorityQueue.add(score[i]);
            if (priorityQueue.size() > k) {
                priorityQueue.poll();
            }

            answer[i] = priorityQueue.peek();
        }



        return answer;
    }
}

• PriorityQueue는 자동으로 원소들을 오름차순으로 정렬
• priorityQueue.peek()를 통해 가장 낮은 점수를 answer 배열에 저장