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

문제 풀이

---

이번 명예의 전당(1) 문제의 경우 많은 분들이 우선순위 큐를 많이들 사용하는 것 같았는데, 필자는 우선순위 큐에 대한 공부가 부족하여 ArrayList를 활용하여 풀었다.
일단은 ArrayList를 활용한 풀이 위주로 해설을 진행하고 추후 우선순위 큐를 학습한 후 다시 한번 풀어볼 예정이다.

아이디어 도출

주어진 score의 길이가 일차가 되고, score의 원소, 즉 점수를 높은 점수순으로 k 만큼 누적해가며 최하위 점수를 구해내야 한다.
여기서 ArrayList를 활용하는 원리는 간단하다.

• k만큼의 일차까지는 명예의 전당에 순서대로 그대로 등록한다.
• 명예의 전당 자리가 꽉 찬 이후의 점수의 경우, 명예의 전당의 최하위 점수와 비교하여 명예의 전당에 등록한다.
  • 이 때, 명예의 전당 점수는 오름차순으로 정렬을 하여 매일 발표되는 점수와 비교하여 명예의 전당에 등록한다.
• 일차(score.length) 별로 명예의 전당의 최하위 점수를 찾으면 된다.

말로 설명하면 좀 이해하기 어려울 수 있으니 바로 코드를 작성해보자.

int[] answer = new int[score.length];
ArrayList<Integer> glory = new ArrayList<>();

매일 발표되는 명예의 전당의 최하위 점수를 담을 answer 배열과 매일 k만큼의 점수를 가지고 있을 ArrayList를 하나 선언하자.

for(int i=0; i<score.length; i++) {
    if(glory.size() < k) {
        glory.add(score[i]);
        Collections.sort(glory);
    }
    else {
        if(score[i] > glory.get(0)) {
            glory.set(0, score[i]);
            Collections.sort(glory);
        }
    }
    answer[i] = glory.get(0);
}

이제 매일 발표되는 점수들을 가지고 명예의 전당에 등록 여부를 가리면 된다. 그 과정은 다음과 같다.

1. 명예의 전당 자리가 꽉 찰 때까지는 매일 발표되는 점수를 그대로 등록시키고 정렬한다.
2. 명예의 전당 자리가 꽉 찬 이후부터는 매일 발표되는 점수와 명예의 전당 최하위 점수와 비교하여 발표되는 점수가 더 클 경우 명예의 전당에 등록한 후 정렬한다.
3. 매일 명예의 전당의 최하위 점수를 answer 배열에 담는다.

모든 경우마다 glory ArrayList를 정렬하는 이유는 최하위 점수를 알고 있어야 하기 때문이다.

작성 코드

---

import java.util.*;

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

        return answer;
    }
    public static void main(String[] args){
        Solution sol = new Solution();
        int k = 4;
        int[] score = new int[]{0, 300, 40, 300, 20, 70, 150, 50, 500, 1000};
        sol.solution(k,score);
    }
}

회고

• 우선순위 큐를 알고 있었다면 더 쉽게 풀 수 있었지만 ArrayList만으로도 쉽게 풀 수 있었던 문제였다. 추후 꼭 우선순위 큐를 활용하여 다시 풀어봐야겠다.