프로그래머스 [연습문제 / 명예의 전당 (1)](C++) -yes6686- 티스토리

프로그래머스 문제 풀이: 명예의 전당 (1)

---

문제 링크: 문제 보기

문제 설명:

매일 발표된 가수의 점수 중, 명예의 전당에 오를 수 있는 k개의 점수를 유지하면서, 그날의 최하위 점수를 기록하는 문제입니다. 명예의 전당 점수는 내림차순으로 유지되며, k개 이상이면 가장 낮은 점수보다 더 높은 점수만 등록됩니다.

---

문제 해결 코드

#include <string>
#include <vector>

using namespace std;

vector<int> arr; // 명예의 전당 점수 저장용

vector<int> solution(int k, vector<int> score) {
    vector<int> answer;
    
    arr.push_back(score[0]);
    answer.push_back(score[0]);

    for (int i = 1; i < score.size(); i++) {
        // k개 미만이면 무조건 추가
        if (arr.size() < k) {
            arr.push_back(score[i]);
        }
        // k개인 경우, 최하위 점수보다 높으면 교체
        else if (arr[arr.size() - 1] < score[i]) {
            arr[arr.size() - 1] = score[i];
        }

        // 삽입 정렬 방식으로 내림차순 유지
        for (int j = arr.size() - 1; j > 0; j--) {
            if (arr[j] > arr[j - 1]) {
                swap(arr[j], arr[j - 1]);
            } else {
                break;
            }
        }

        // 현재 명예의 전당 최하위 점수 추가
        answer.push_back(arr[arr.size() - 1]);
    }

    return answer;
}

---

코드 설명

• 핵심 알고리즘: 제한된 크기의 내림차순 배열을 유지하며, 그 배열의 마지막 값을 매번 결과에 저장합니다.
• 구현 세부사항:
• 처음 등장한 점수는 무조건 등록합니다.
• 배열의 크기가 k 이상일 경우, 새로운 점수가 최하위 점수보다 크면 교체합니다.
• 삽입 정렬 방식으로 점수를 내림차순 정렬하여 마지막 원소가 항상 최하위 점수입니다.
• 시간 복잡도 분석:
• 최악의 경우 매일 O(k)의 정렬이 필요하므로 총 O(n * k)
• n = score 크기, k는 작으므로 일반적으로 효율적

---

결과

이 코드는 명예의 전당 점수를 효율적으로 유지하며, 매일의 최하위 점수를 정확히 출력합니다.

다른 접근 방식으로는 priority_queue (min-heap)를 활용하여 항상 최하위 점수를 빠르게 관리할 수 있습니다. 특히 k가 매우 크거나 점수 입력이 많을 경우 힙 구조가 성능상 더 유리할 수 있습니다.