[프로그래머스/Lv.1] 명예의 전당(1) - Java

📌 문제

프로그래머스

📌 풀이 - 배열 사용

나는 이 문제를 그냥 배열을 이용해 풀었지만, 다른 사람들의 코드를 보니 우선 순위 큐를 사용한 사람들이 많았다. 실제로 배열을 사용한 코드와 우선 순위 큐를 사용한 코드를 비교해보니 우선 순위 큐가 더 빨랐다. 이번 문제를 통해 우선 순위 큐를 사용하는 방법을 공부해보는 것이 좋겠다.

배열 사용(왼) / 우선순위 큐 사용(오)

 

내가 처음 작성한 답안은 배열과 정렬을 이용하였다. 먼저 명예의 전당에 들어가는 점수를 저장하는 hallOfFameScores 배열과 명예의 전당의 최하위 점수를 저장하는 answer 배열을 만들었다.

 

그리고나서 score 배열을 돌며 다음 2가지의 조건에 따라 배열이 채워진다.

• i가 k보다 작을 경우(모든 출연 가수의 점수가 명예의 전당에 오르는 경우)
  • 명예의 전당 0번째에 점수를 넣는다.
  • 명예의 전당에 들어간 점수를 오름차순으로 정렬한다.
  • 결과 배열에 명예의 전당의 점수를 뒤에서부터 가져와 넣는다.
• i가 k보다 클 경우(명예의 전당 k번째 점수보다 점수가 높은 사람이 명예의 전당에 오르는 경우)
  • 점수가 명예의 전당 0번째 점수(제일 낮은 점수)보다 크거나 같으면 해당 점수를 0번째 배열에 넣는다.
  • 명예의 전당에 들어간 점수를 오름차순으로 정렬한다.
  • 결과 배열에 명예의 전당의 0번째 점수를 넣는다.

for (int i = 0; i < score.length; i++) {
    if (i < k) {
        hallOfFameScores[0] = score[i];
        Arrays.sort(hallOfFameScores);
        answer[i] = hallOfFameScores[k-i-1];
    } else {
        if (score[i] >= hallOfFameScores[0]) hallOfFameScores[0] = score[i];
        Arrays.sort(hallOfFameScores);
        answer[i] = hallOfFameScores[0];
    }
}

📌 풀이 - 우선 순위 큐 사용

우선순위 큐를 사용하니 배열보다 간단하게 풀 수 있었다. 우선 순위 큐는 기본적으로 낮은 숫자 순으로 정렬하기 때문에 이번 문제에서는 그냥 선언해서 이용하면 된다. 만약 높은 숫자를 우선 순위로 두려면 아래와 같이 선언할 때 Collections.reverseOrder()를 추가해주면 된다.

// 낮은 순자가 우선 순위일 때
PriorityQueue<Integer> priorityQueueLowest = new PriorityQueue<>();
// 높은 순자가 우선 순위일 때
PriorityQueue<Integer> priorityQueueHeighest = new PriorityQueue<>(Collections.reverseOrder());

 

우선 순위대로 나오기 때문에 이렇게 간단하게 구현할 수 있다.

for(int i = 0; i < score.length; i++){
    pq.add(score[i]);
    if(pq.size() > k) pq.poll();
    answer[i] = pq.peek();
}

📌 전체 코드

배열을 이용한 풀이

import java.util.*;

class Solution {
    public int[] solution(int k, int[] score) {
        int[] answer = new int[score.length];
        int[] hallOfFameScores = new int[k];
        
        for (int i = 0; i < score.length; i++) {
            if (i < k) {
                hallOfFameScores[0] = score[i];
                Arrays.sort(hallOfFameScores);
                answer[i] = hallOfFameScores[k-i-1];
            } else {
                if (score[i] >= hallOfFameScores[0]) hallOfFameScores[0] = score[i];
                Arrays.sort(hallOfFameScores);
                answer[i] = hallOfFameScores[0];
            }
    }
        
        return answer;
    }
}

 

우선 순위 큐를 이용한 풀이

import java.util.*;

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

        return answer;
    }
}