[프로그래머스/Day 10] 명예의 전당 (1) - 복잡한 구현에서 단순한 로직으로(Vector vs Priority Queue)

1. 문제 개요

프로그래머스의 '명예의 전당 (1)' 문제를 풀면서 겪었던 시행착오와 해결 과정을 정리합니다.

이 문제는 매일 가수의 점수가 주어질 때, 상위 k번째 이내의 점수들(명예의 전당) 중 최하위 점수를 매일 발표하는 문제입니다.

 

---

2. 첫 번째 접근: 복잡한 구현 (시행착오)

처음에는 벡터를 명예의 전당(honor) 그 자체로 보고, 새로운 점수가 들어올 때마다 적절한 위치를 찾아 교체하려고 했습니다.

 

[초기 의사코드]

1. 명예의 전당 벡터를 미리 k 크기만큼 -1로 초기화한다.
2. 새로운 점수가 들어오면 명예의 전당 말석과 비교한다.
3. 새 점수가 더 크다면 말석을 내보낸다.
4. 처음부터 순회하며 들어갈 자리를 찾는다.
5. 명예의 전당 점수를 내림차순 정렬한다.
6. 매일 명예의 전당 최하위 점수를 결과에 더한다.

하지만 막상 코드로 구현하려니 "들어갈 자리를 찾는다"는 부분에서 막혔습니다.

벡터의 크기를 고정하고 인덱스를 조작하려다 보니 코드가 꼬이기 시작했습니다.

vector<int> solution(int k, vector<int> score) {
    vector<int> answer;
    
    // 1. 명예의 전당 벡터를 미리 k 크기만큼 -1로 초기화한다.
    vector<int> honor(k, -1);
    
    for(int sco : score)
    {
        // 2. 새로운 점수가 들어오면 명예의 전당 말석(최하위)과 비교한다.
        if(sco > honor[honor.size() - 1])
        {
            // 3. 새 점수가 더 크다면 말석을 내보낸다
            honor.pop_back();
            
            // 4. 처음부터 순회하며 들어갈 자리를 찾는다.
            
        }
        
        // 5. 명예의 전당 점수를 내림차순 정렬한다.
        sort(honor.begin(), honor.end(), greater<int>());
        
        // 6. 매일 명예의 전당 최하위 점수를 결과에 더한다.
        answer.push_back(honor[honor.size() - 1]);
    }
    
    return answer;
}

 

---

3. 두 번째 접근: 로직의 단순화

생각을 바꿔보았습니다. "굳이 들어갈 자리를 미리 찾을 필요가 있을까?"

일단 다 넣고, 정렬한 뒤에, 넘치는 점수를 자르면 그만이었습니다.

 

[개선된 의사코드]

1. 점수를 명예의 전당에 넣는다.
2. 명예의 전당을 내림차순으로 정렬한다.
3. 만약 명예의 전당 정원을 초과했다면? -> 말석을 탈락시킨다.
4. 현재 명예의 전당의 최하위 점수를 결과에 저장한다.

vector<int> solution(int k, vector<int> score) {
    vector<int> answer;
    vector<int> honor; // 초기 크기 지정 없이 빈 벡터로 시작
    
    for(int sco : score)
    {
        // 1. 점수를 명예의 전당에 넣는다.
        honor.push_back(sco);
        
        // 2. 명예의 전당을 내림차순 정렬합니다.
        sort(honor.begin(), honor.end(), greater<int>());
        
        // 3. 만약 명예의 전당 정원을 초과했다면?
        if(honor.size() > k)
        {
            // 말석을 탈락시킨다.
            honor.pop_back();
        }
        
        // 4. 현재 명예의 전당의 최하위 점수를 결과에 저장한다.
        answer.push_back(honor.back());
    }
    
    return answer;
}

 

---

4. 더 나은 방법: 우선순위 큐

문제를 풀고 나서 다른 사람들의 풀이를 찾아보니,

이 문제는 우선순위 큐(Priority Queue)를 사용하면 훨씬 효율적으로 풀 수 있다는 것을 알게 되었습니다.

 

항상 "상위 k개 중 최솟값"만 알면 됩니다.

즉, Min Heap 구조를 사용하면 매번 정렬(sort)할 필요 없이, 가장 작은 값이 항상 top에 오게 됩니다.

 

#include <vector>
#include <queue> 

using namespace std;

vector<int> solution(int k, vector<int> score) {
    vector<int> answer;
    // 오름차순 우선순위 큐 (작은 숫자가 위로 옴 == Min Heap)
    priority_queue<int, vector<int>, greater<int>> pq; 
    
    for(int sco : score) {
        pq.push(sco); // 점수 추가 (자동 정렬됨)
        
        // 명예의 전당이 꽉 찼다면
        if (pq.size() > k) {
            pq.pop(); // 가장 작은 점수(top)를 버림
        }
        
        // 남은 것 중 가장 작은 점수가 명예의 전당 턱걸이 점수
        answer.push_back(pq.top());
    }
    
    return answer;
}

 

---

5. 정리

• Vector + Sort: 구현이 직관적이다. 매번 정렬하므로 O(N · K log K) 시간 복잡도를 가진다.
• Priority Queue: 삽입/삭제 시 O(log K)가 소요되므로 전체 O(N log K)로 더 효율적이다. 특히 K가 커질수록 성능 차이가 날 것이다.
  • priority_queue의 기본은 내림차순(Max Heap)이지만, greater<int>를 추가하면 오름차순(Min Heap)으로 동작한다

처음에는 익숙한 벡터로 접근하다 길을 잃었지만, 로직을 단순화하여 문제를 해결했고, 더 나아가 자료구조를 활용한 최적화 방법까지 학습할 수 있었습니다.