코딩테스트 연습 - 명예의 전당

김원기·2025년 1월 4일

Java 코딩테스트 연습

코딩테스트

목록 보기

15/21

이번에 풀어본 문제는 명예의 전당이라는 문제다
https://school.programmers.co.kr/learn/courses/30/lessons/138477

문제를 보면 k 일이 주어지고 k 일 까지의 가수의 점수는 모두 명예의 전당에 등록되지만 k+1일 부터의 점수는 k번째의 순서보다 점수가 높을 경우 명예의 전당에 등록된다고 한다.

명예의 전당 목록의 점수의 개수 k, 1일부터 마지막 날까지 출연한 가수들의 점수인 score가 주어진다.

문제 풀이

일단 나는 문제를 풀 때 ArrayList를 사용했다.

문제를 풀면서 3개의 ArrayList를 사용했는데

// 명예의 전당에 점수를 담을 배열
ArrayList<Integer> honor = new ArrayList<>();

// score를 다룰 수 있도록 동적 배열로 변경
ArrayList<Integer> scores = new ArrayList<>();
for(int s : score) {
    scores.add(s);
}
        
// 결과 값을 담을 동적 배열 역시 생성
ArrayList<Integer> presentateScore = new ArrayList<>();

위와 같은 3개의 리스트를 생성하여 각각을 사용했다.

사실 여기서 score가 이미 주어지기 때문에 굳이 scores라는 동적 리스트를 생성할 필요는 없었지만 추가적으로 사용할 수 있는 메서드의 편의성을 위해 생성하였다.

3개의 리스트를 통해 하는 행동은 다음과 같다.

scores 만큼 반복을 수행하면서 명예의 전당에 점수를 삽입한다.
k일 까지는 명예의 전당에 그대로 등록된다.
k일 이후 부터는 새로운 점수가 명예의 전당의 k번째 점수보다 높아야 한다.

// scores 수 만큼 반복을 돌리면서 명예의 전당에 점수를 삽입
    for(int scorePerDay : scores) {
        // k 크기보다 작다면 그대로 honor에 포함시킨다.
        honor.add(scorePerDay);
            
        if(honor.size() <= k) {
                
            // honor에서 최소값을 발표한다.
            presentateScore.add(Collections.min(honor));
        }
        // k의 크기보다 size가 크게 들어왔다면 honor 내부의 값과 scorePerDay를 비교하여 큰 값을 honor에 포함시킨다.
        if(honor.size() > k) {
            // 가장 작은 값은 삭제하고
            honor.remove(Collections.min(honor));
            // 두 번째 값을 발표한다.
            presentateScore.add(Collections.min(honor));
        }
    }

나는 문제를 풀면서 k번째를 굳이 생각하기 보단 점수가 더 높아야 한다는 것에 집중했기 때문에 최소값을 통한 리스트 삭제로 해당 문제의 풀이를 구현하였다.

그리고 다 구했을 경우 presentateScore를 return해주면 된다.
다만 매번 귀찮아서 int[] 형태의 Solution 메서드를 바꾸지 않았으므로 Stream을 이용하여
ArrayList를 변경하도록 하겠다.

 // Stream을 이용하여 변경
    int[] answer = presentateScore.stream()
                                  .mapToInt(Integer::intValue)
                                  .toArray();

전체 코드

import java.util.*;
class Solution {
    public int[] solution(int k, int[] score) {
        // System.out.println(honor.length);
        
        // 명예의 전당에 점수를 담을 배열
        ArrayList<Integer> honor = new ArrayList<>();

        // score를 다룰 수 있도록 동적 배열로 변경
        ArrayList<Integer> scores = new ArrayList<>();
        for(int s : score) {
            scores.add(s);
        }
        
        // 결과 값을 담을 동적 배열 역시 생성
        ArrayList<Integer> presentateScore = new ArrayList<>();
        
        // scores 수 만큼 반복을 돌리면서 명예의 전당에 점수를 삽입
        for(int scorePerDay : scores) {
            // k 크기보다 작다면 그대로 honor에 포함시킨다.
            honor.add(scorePerDay);
            
            if(honor.size() <= k) {
                
                // honor에서 최소값을 발표한다.
                presentateScore.add(Collections.min(honor));
            }
            // k의 크기보다 size가 크게 들어왔다면 honor 내부의 값과 scorePerDay를 비교하여 큰 값을 honor에 포함시킨다.
            if(honor.size() > k) {
                // 가장 작은 값은 삭제하고
                honor.remove(Collections.min(honor));
                // 두 번째 값을 발표한다.
                presentateScore.add(Collections.min(honor));
            }
        }
        
        // Stream을 이용하여 변경
        int[] answer = presentateScore.stream()
                                      .mapToInt(Integer::intValue)
                                      .toArray();
        return answer;
    }
}

문제점

내가 이 문제를 풀면서 느꼈던 문제는 3번의 ArrayList 생성이다.
Java는 ArrayList가 사용하는 메모리 소비를 효율적으로 관리하지만 3개를 생성하는 것 보다 더 좋은 방법이 있을 것이라 생각된다.

또한 Collection.min() 자체는 리스트를 순회하면서 최소값을 찾기 때문에 리스트가 크다면 성능저하 역시 고려될 문제다.

그래서 해결한 방법은 PriorityQueue 를 사용하는 방법이다.

PriorityQueue

우선순위 큐의 사용이다.
PriorityQueue의 특징은 다음과 같다.

PriorityQueue는 항상 최소값을 빠르게 얻을 수 있는 자료구조다.
peek()으로 최소값을 바로 얻을 수 있다.
추가 및 삭제 연산이 O(log k)로 효율적이며, k가 작다면 메모리 사용량과 연산 속도가 모두 개선된다.

뿐만아니라 여러개의 리스트를 생성하지 않고 기존의 score를 사용하면서 우선순위 큐를 생성하면 자체적인 메모리 역시 절약된다.

개선된 코드

import java.util.*;

class Solution {
    public int[] solution(int k, int[] score) {
        // 명예의 전당에 점수를 저장할 우선순위 큐 (최소 힙)
        PriorityQueue<Integer> honor = new PriorityQueue<>();

        // 결과값을 담을 배열
        int[] answer = new int[score.length];
        
        for (int i = 0; i < score.length; i++) {
            // 점수를 우선순위 큐에 추가
            honor.add(score[i]);
            
            // 명예의 전당 크기가 k를 초과하면 가장 작은 값 제거
            if (honor.size() > k) {
                honor.poll();
            }
            
            // 현재 명예의 전당에서 가장 작은 값 저장
            answer[i] = honor.peek();
        }
        
        return answer;
    }
}