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

PriorityQueue 이용하기

명예의 전당 (1) : Level1

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

프로그래머스

 

 

 

첫 번째 작성한 코드

import java.util.*;

class Solution {
    public int[] solution(int k, int[] score) {
        ArrayList<Integer> al = new ArrayList<>();
        int[] answer = new int[score.length];
        
        if (k <= score.length) {
            for (int i = 0; i < k; i++) {
                al.add(score[i]);
                Collections.sort(al);
                answer[i] = al.get(0);
            }

            for (int i = k; i < score.length; i++) {
                if (score[i] > al.get(0)) {
                    al.remove(0);
                    al.add(score[i]);
                    Collections.sort(al);
                }
                answer[i] = al.get(0);
            }
        } else {
            for (int i = 0; i < score.length; i++) {
                al.add(score[i]);
                Collections.sort(al);
                answer[i] = al.get(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]); // 현재 가수의 점수를 우선순위 큐에 추가
            
            // 우선순위 큐의 크기가 k를 초과하면, 큐에서 가장 작은 값을 제거 
            // 이렇게 함으로써 명예의 전당에는 상위 k개의 점수만 유지됨
            if (pq.size() > k) {
                pq.poll();
            }
            
            // 현재까지의 명예의 전당에 있는 최하위 점수를 배열에 저장 
            // PriorityQueue의 peek 메서드는 큐에서 가장 작은 값을 반환
            answer[i] = pq.peek();
        }

        return answer;
    }
}

 

 

 

PriorityQueue

내부적으로 최소 힙(Min Heap)을 사용하는 자료구조이다.

최소 힙은 원소들을 낮은 값부터 높은 값 순서로 정렬하여 저장하는 특징이 있다.

문제에서는 명예의 전당에 포함된 가수의 최하위 점수를 계속 추적해야 하기 때문에, 가장 낮은 점수를 빠르게 찾기 위해 최소 힙을 활용하는 것이 효율적이다.

PriorityQueue를 사용하면 원소를 삽입하거나 제거할 때마다 자동으로 최소 힙의 성질을 유지한다.

따라서 명예의 전당에서 가장 작은 점수를 빠르게 찾아내는데 효과적이다.

만약 일반적인 Queue를 사용한다면, 원소를 삽입하거나 제거할 때마다 모든 원소를 탐색하여 최소값을 찾아야 하므로 시간 복잡도가 높아질 수 있다.

=> 문제에서 PriorityQueue를 사용하는 것은 최소 힙의 특성을 활용하여 효율적으로 명예의 전당에서 최하위 점수를 관리하기 위함이다.

 

---

 

 

문제점 : 첫 번째 코드를 통해 문제를 해결하였지만 코드 가독성이 너무 떨어진다고 느꼈다.

해결 방법 : 코드 가독성을 높이기 위해 두 번째 코드처럼 PriorityQueue를 이용하도록 했다.

깨달은 바 : 코드 가독성을 위해 다양한 시도를 하여 코드를 작성하도록 해야겠다는 생각이 들었다.