선밥의 공부하는 블로그

명예의 전당 (1)

문제 링크

명예의 전당 (1)

분석

score배열을 순회해 값을 저장합니다.
저장 할 때 요소들의 값은 내림차순으로 정렬되어야 합니다.
이때 저장한 자료구조에서 k 크기를 유지해야 합니다.

이런식으로 정렬된 값 중 최하위 값을 효율적으로 찾는 문제입니다.

std::vector와 정렬을 사용한 방법이나 std::priority_queue를 사용한 방법으로 풀 수 있습니다.

풀이

std::vector와 정렬을 사용한 풀이입니다.

#include <vector>
#include <algorithm>

std::vector<int> solution(int k, std::vector<int> score) {
    std::vector<int> answer;
    std::vector<int> temp;
    
    for (int i = 0; i < score.size(); ++i)
    {
        temp.push_back(score[i]);
        
        std::sort(temp.rbegin(), temp.rend());
        
        if (k < temp.size())
        {
            temp.pop_back();
        }
        
        answer.push_back(temp.back());
    }
    
    return answer;
}

std::priority_queue를 사용한 방법입니다.

#include <vector>
#include <queue>

std::vector<int> solution(int k, std::vector<int> score) {
    std::vector<int> answer;
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
    
    for (auto e : score)
    {
        minHeap.push(e);
        
        if (k < minHeap.size())
        {
            minHeap.pop();
        }
        
        answer.push_back(minHeap.top());
    }
    
    return answer;
}

std::priority_queue는 기본적으로 Top에 가작 큰 값이 저장되는 내림차순이므로, 최소값부터 시작하는 오름차순으로 정렬하기 위해 std::greater<int>를 사용했습니다.

성능 요약

std::vector와 정렬을 사용한 성능입니다.

시간 복잡도는 반복문과 정렬 함수로 인해 $O(n \times k \times log \, k)$입니다.

공간 복잡도는 $O(n)$입니다.

테스트 1 〉 통과 (0.02ms, 4.21MB)
테스트 2 〉 통과 (0.01ms, 4.05MB)
테스트 3 〉 통과 (0.01ms, 4.21MB)
테스트 4 〉 통과 (0.01ms, 4.07MB)
테스트 5 〉 통과 (0.02ms, 4.21MB)
테스트 6 〉 통과 (0.01ms, 4.01MB)
테스트 7 〉 통과 (0.02ms, 4.2MB)
테스트 8 〉 통과 (0.02ms, 4.18MB)
테스트 9 〉 통과 (0.02ms, 4.14MB)
테스트 10 〉 통과 (0.03ms, 4.02MB)
테스트 11 〉 통과 (0.04ms, 4.13MB)
테스트 12 〉 통과 (0.40ms, 4.14MB)
테스트 13 〉 통과 (0.45ms, 3.79MB)
테스트 14 〉 통과 (0.22ms, 4.2MB)
테스트 15 〉 통과 (0.56ms, 4.14MB)
테스트 16 〉 통과 (0.56ms, 4.2MB)
테스트 17 〉 통과 (0.59ms, 4.13MB)
테스트 18 〉 통과 (0.56ms, 4.2MB)
테스트 19 〉 통과 (0.26ms, 3.83MB)
테스트 20 〉 통과 (0.22ms, 4.13MB)
테스트 21 〉 통과 (0.33ms, 4.15MB)
테스트 22 〉 통과 (0.21ms, 4.21MB)
테스트 23 〉 통과 (0.21ms, 4.08MB)
테스트 24 〉 통과 (0.23ms, 4.2MB)
테스트 25 〉 통과 (0.38ms, 4.2MB)
테스트 26 〉 통과 (0.01ms, 4.2MB)

std::priority_queue를 사용한 성능입니다.

시간 복잡도는 k에 의해 크기가 제한되어, 원소를 추가하거나 삭제하므로 $O(log \, k)$이며, 반복문으로 score를 순회하기 때문에 $O(n \times log \, k)$입니다.

공간 복잡도는 $O(n)$입니다.

테스트 1 〉 통과 (0.01ms, 3.7MB)
테스트 2 〉 통과 (0.01ms, 4.2MB)
테스트 3 〉 통과 (0.01ms, 4.23MB)
테스트 4 〉 통과 (0.01ms, 4.02MB)
테스트 5 〉 통과 (0.01ms, 4.2MB)
테스트 6 〉 통과 (0.01ms, 3.63MB)
테스트 7 〉 통과 (0.01ms, 4.21MB)
테스트 8 〉 통과 (0.01ms, 4.22MB)
테스트 9 〉 통과 (0.01ms, 4.19MB)
테스트 10 〉 통과 (0.02ms, 4.23MB)
테스트 11 〉 통과 (0.02ms, 4.16MB)
테스트 12 〉 통과 (0.12ms, 4.21MB)
테스트 13 〉 통과 (0.11ms, 4.17MB)
테스트 14 〉 통과 (0.12ms, 4.22MB)
테스트 15 〉 통과 (0.23ms, 4.21MB)
테스트 16 〉 통과 (0.23ms, 4.2MB)
테스트 17 〉 통과 (0.23ms, 4.16MB)
테스트 18 〉 통과 (0.22ms, 4.15MB)
테스트 19 〉 통과 (0.20ms, 3.8MB)
테스트 20 〉 통과 (0.22ms, 4.16MB)
테스트 21 〉 통과 (0.20ms, 4.18MB)
테스트 22 〉 통과 (0.22ms, 4.21MB)
테스트 23 〉 통과 (0.22ms, 3.92MB)
테스트 24 〉 통과 (0.22ms, 4.02MB)
테스트 25 〉 통과 (0.23ms, 4.16MB)
테스트 26 〉 통과 (0.01ms, 4.11MB)

Programmers 카테고리 내 다른 글 보러가기

댓글남기기

최근 글