[알고리즘] 명예의 전당 (Hall of Fame Problem)

Algorithm

[알고리즘] 명예의 전당 (Hall of Fame Problem)

montmer27 2026. 3. 20. 10:02

문제 본문 (Problem Presentation)

"명예의 전당"이라는 TV 프로그램에서는 매일 1명의 가수가 노래를 부르고, 시청자들의 문자 투표수로 가수에게 점수를 부여합니다. 매일 출연한 가수의 점수가 지금까지 출연 가수들의 점수 중 상위 k번째 이내이면 해당 가수의 점수를 명예의 전당이라는 목록에 올려 기념합니다. 즉 프로그램 시작 이후 초기에 k일까지는 모든 출연 가수의 점수가 명예의 전당에 오르게 됩니다. k일 다음부터는 출연 가수의 점수가 기존의 명예의 전당 목록의 k번째 순위의 가수 점수보다 더 높으면, 출연 가수의 점수가 명예의 전당에 오르게 되고 기존의 k번째 순위의 점수는 명예의 전당에서 내려오게 됩니다.
이 프로그램에서는 매일 "명예의 전당"의 최하위 점수를 발표합니다. 예를 들어, k = 3이고, 7일 동안 진행된 가수의 점수가 [10, 100, 20, 150, 1, 100, 200]이라면, 명예의 전당에서 발표된 점수는 아래의 그림과 같이 [10, 10, 10, 20, 20, 100, 100]입니다.

명예의 전당 목록의 점수의 개수 k, 1일부터 마지막 날까지 출연한 가수들의 점수인 score가 주어졌을 때, 매일 발표된 명예의 전당의 최하위 점수를 return하는 solution 함수를 완성해주세요.

나의 풀이 (My Solution)

3줄 접근 (3-sentence approach)

k일차까지는 새 엔트리가 들어올 때마다 최소값을 구하고, k+1일차부터는 k번째 값을 구해야 한다.
새 엔트리가 들어올 때마다 k번째 값은 달라져야 하므로, 매번 정렬이 일어나야 한다.
퀵 정렬인 Arrays.sort()나 Collections.sort()가 유리하다. 요소의 삽입과 삭제가 빈번하게 일어나므로 ArrayList를 활용한 Collections.sort()를 이용하자.

코드 (Code)

import java.util.Collections;
import java.util.List;
import java.util.ArrayList;

class Solution {
    public int[] solution(int k, int[] score) {
        List<Integer> list = new ArrayList<>();
        list.add(score[0]);
        int[] answer = new int[score.length];
        int min = score[0];
        answer[0] = min;
        for(int i = 1; i < Math.min(k, score.length); i++) {
            min = Math.min(min, score[i]);
            answer[i] = min;
            list.add(score[i]);
        }
        if(k <= score.length) {
            for(int i = k; i < score.length; i++) {
                list.add(score[i]);
                Collections.sort(list, Collections.reverseOrder());
                answer[i] = list.get(k-1);
            }
        }
        
        return answer;
    }
}

import java.util.Collections;
import java.util.List;
import java.util.ArrayList;

class Solution {
    public int[] solution(int k, int[] score) {
        List<Integer> list = new ArrayList<>();
        list.add(score[0]);
        // 실수 1: 고정 길이의 배열 선언을 잘못함
        int[] answer = new int[score.length];
        int min = score[0];
        answer[0] = min;
        // 실수 5 해답: k 또는 score.length 중 더 작은 값만큼 아래 루프를 반복해야 함.
        for(int i = 1; i < Math.min(k, score.length); i++) {
            // 실수 2. 최솟값이 갱신되지 않아 계속 동일한 값으로 비교함
            // 실수 5. 여기에도 k > score.length인 경우에 대한 방어 코드 누락
            min = Math.min(min, score[i]);
            answer[i] = min;
            list.add(score[i]);
        }
        // 실수 3. k가 score.length보다 큰 경우 방어 코드 필요
        if(k <= score.length) {
            for(int i = k; i < score.length; i++) {
                list.add(score[i]); // 엔트리 추가
                // 실수 4. 내림차순으로 정렬해야 하는데 오름차순(기본값)으로 정렬함
                Collections.sort(list, Collections.reverseOrder());
                answer[i] = list.get(k-1); // 0-based index이므로 k번째는 (k-1) 위치에
            }
        }
        
        return answer;
    }
}

/*
k일차까지는 새 엔트리가 들어올 때마다 최소값을 구하고,
k+1일차부터는 k번째 값을 구해야 한다.
새 엔트리가 들어올 때마다 k번째 값은 달라져야 하므로, 매번 정렬이 일어나야 한다.
퀵 정렬인 Arrays.sort()나 Collections.sort()가 유리하다.
요소의 삽입과 삭제가 빈번하게 일어나므로 ArrayList를 활용한 Collections.sort()를 이용하자.
*/

분석 (Analysis)

시간 복잡도 (Time Complexity) : O(n² log n)
공간 복잡도 (Space Complexity) : O(n)
사용하는 자료구조 (Data Structure) : ArrayList

장점

1. 문제를 정확히 이해하고 구현했다. k일 이전과 이후를 명확히 구분하여 로직을 분리한 점이 좋습니다. 문제의 핵심 조건을 놓치지 않고 두 구간을 각각 올바르게 처리했습니다.

2. 방어 코드(Edge Case)를 의식했다. k > score.length인 경우를 Math.min(k, score.length)와 if(k <= score.length) 조건으로 처리한 점은 긍정적입니다. 면접관은 경계 조건을 고려하는 지원자를 선호합니다.

3. 주석이 풍부하고 자기 회고가 담겨 있다. 어디서 실수했고 왜 수정했는지를 주석으로 남긴 것은 디버깅 능력과 반성적 사고를 보여줍니다. 실무에서도 중요한 역량입니다.

4. 적절한 자료구조를 선택했다. 고정 배열 대신 동적 크기의 ArrayList를 선택한 이유(요소의 삽입/삭제가 빈번)를 스스로 설명하고 있어, 자료구조 선택에 대한 근거가 있습니다.

한계

1. 매 반복마다 전체 리스트를 정렬하는 것은 비효율적이다. Collections.sort()를 루프 안에서 반복 호출하면 O(n² log n)이 됩니다. 이 문제는 n ≤ 1,000이라 통과했지만, 면접관은 "n이 100만이라면 어떻게 하겠느냐?"고 반드시 물어볼 것입니다. PriorityQueue(최소 힙)를 쓰면 O(n log k)로 해결할 수 있다는 점을 모른다면 감점 요인이 됩니다.

2. 리스트에서 k번째 이후 요소를 제거하지 않는다. 명예의 전당은 상위 k개만 유지해야 하는데, 이 코드는 점수를 계속 리스트에 누적합니다. get(k-1)로 결과는 올바르게 나오지만, 논리적으로는 k개 초과의 데이터를 불필요하게 유지하는 것이며, 면접관에게 "왜 리스트를 k개로 유지하지 않았나요?"라는 질문을 받을 수 있습니다.

3. 코드 구조가 다소 중복적이고 복잡하다. k일 이전 구간과 이후 구간을 별도 루프로 분리한 것은 이해는 되지만, 하나의 루프로 통합하면 더 간결하고 읽기 쉬운 코드가 됩니다. 면접에서는 간결성과 가독성도 평가 대상입니다.

4. 변수명 min이 역할을 충분히 설명하지 못한다. k일 이전에는 최솟값 추적용으로 사용되지만, k일 이후에는 사용되지 않습니다. 역할이 제한적임에도 전체 메서드 스코프에 선언되어 있어 코드의 의도를 파악하는 데 약간의 혼란을 줄 수 있습니다.

다른 답안 # 1 - PriorityQueue 활용

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;
    }
}

기본 접근

최소 힙을 크기 k로 유지합니다. 매일 새 점수를 힙에 넣고, 크기가 k를 초과하면 가장 작은 값을 poll()로 제거합니다. 힙의 루트(가장 작은 값)가 곧 명예의 전당 최하위 점수이므로 peek()으로 바로 가져옵니다.

분석

시간 복잡도: O(n log k) — n번 반복하며 매번 힙 삽입/삭제가 O(log k)입니다.
공간 복잡도: O(k) — 힙 크기를 항상 k로 유지하므로 추가 공간이 k에 비례합니다.
사용하는 자료구조: PriorityQueue (최소 힙)

장점

코드가 매우 간결함(핵심 로직 5줄)
힙의 특성상 k번째 최솟값을 항상 O(1)에 조회할 수 있어 효율적입니다.
k일 이전/이후 구간을 분리할 필요 없이 단일 루프로 처리되어 가독성이 뛰어납니다.

한계

PriorityQueue의 내부 동작(최소 힙 구조)을 이해하지 못하면 왜 peek()이 k번째 값을 반환하는지 직관적으로 이해하기 어렵습니다.
힙은 인덱스 기반 접근이 불가능해, 만약 문제 조건이 바뀌어 k번째가 아닌 다른 순위를 요구할 경우 유연성이 떨어집니다.

다른 답안 # 2 - IntStream + Arrays.sort() 활용

import java.util.Arrays;
import java.util.Collections;
import java.util.stream.IntStream;

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

        return IntStream.range(0, score.length)
                .peek(i -> scores[i] = score[i])
                .map(i -> {
                    Arrays.sort(scores, 0, i + 1, Collections.reverseOrder(Integer::compare));
                    return i < k ? scores[i] : scores[k - 1];
                })
                .toArray();
    }
}

기본 접근

Java Stream API를 활용한 함수형 스타일입니다. peek()으로 날짜별 점수를 배열에 누적하고, map() 안에서 매일 0~i 구간을 내림차순 정렬한 뒤, i가 k 미만이면 scores[i](현재까지 최솟값), k 이상이면 scores[k-1](k번째 값)을 반환합니다.

분석

시간 복잡도: O(n² log n) — 매 반복마다 부분 배열을 정렬하며, 정렬 범위가 최대 n까지 커집니다.
공간 복잡도: O(n) — 점수를 누적하는 Integer[] 배열이 n 크기로 유지됩니다.
사용하는 자료구조: 배열 (Integer [])

장점

Java Stream API를 활용한 선언적(declarative) 스타일로, 코드를 함수형으로 작성할 수 있다는 것을 보여줍니다.
solution() 메서드가 단일 return 문으로 구성되어 있어 코드가 매우 압축적입니다. Java의 고급 API 활용 능력을 어필할 수 있습니다.

한계

시간 복잡도가 O(n² log n)으로 비효율적입니다.
또한 peek()을 부수 효과(side effect) 목적으로 사용하는 것은 Stream API의 올바른 사용법이 아니며, 코드의 의도를 파악하기 어렵게 만듭니다. 가독성과 유지보수성 측면에서는 오히려 가장 낮은 평가를 받을 수 있습니다.

인사이트

아직 내가 모르는 자료구조가 많다. 자료구조와 알고리즘 공부에도 시간을 투자해야겠다.
시/공간 복잡도를 표현할 때 그냥 n을 쓰는 것이 아니고 문제의 조건을 활용해서 필요하다면 여러 변수가 들어가야 한다.
Stream API의 올바른 사용법과 잘못된 사용법을 알아보고 싶다.
코드가 압축적이라고 해서 무조건 좋은 것은 아니라는 불문율을 다시 한 번 느낀다.

Github

https://github.com/ginsengcandy/Coding-Test-Practice/commit/03421835e2c85973e00d8752d60e2b7902d5787f

[level 1] Title: 명예의 전당 (1), Time: 17.44 ms, Memory: 88.7 MB -Baekjoo… · ginsengcandy/Coding-Test-Practice@0342183

…nHub

github.com

문제 및 학습 자료 출처

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

프로그래머스

SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프

programmers.co.kr

'Algorithm' 카테고리의 다른 글

[알고리즘] 로또의 최고 순위와 최저 순위 (0)	2026.04.06
[알고리즘] 기사단원의 무기 (0)	2026.04.03
[알고리즘] 콜라 문제: 수학적으로 닫힌 공식으로 환원하기 (0)	2026.03.17
[알고리즘] 푸드 파이트 대회 - StringBuilder, repeat(), reverse() (0)	2026.03.11
[알고리즘] 가장 가까운 같은 글자 찾기: HashMap으로 이중 루프 예방하기 (0)	2026.03.06

현재글[알고리즘] 명예의 전당 (Hall of Fame Problem)

Developing

May my work be of your glory

sql, Algorithm, Junior Developer, 개발자, backend, redis, 부트캠프, 스파르타코딩클럽, Claude, 자바, spring boot, 프로그래머스, kafka, 데이터분석, Git, java, spring, 데이터엔지니어, developer, 백엔드,

Today :
Yesterday :

Developing