명예의 전당 (1)

문제

문제 해석

- score의 길이가 1,000이므로 이중 반복문(O(N^2)까지는 사용해도 충분하다.

- score에서 명예의 전당(HallOfFame)에 기록되고 나면 명예의 전당에 정렬이 필요하다.(algorithm 헤더 사용)

0. 초기에 k일까지는 모든 출연 가수의 점수가 명예의 전당에 오르게 할 것.

1. k번째 순위의 가수 점수보다 더 높으면 
    1-1. 출연 가수의 점수가 명예의 전당에 오르게 되고
    1-2. 기존의 k번째 순위의 점수는 명예의 전당에서 내려오게 된다.

2. 명예의 전당을 정렬한다.

3. 꼴찌를 answer에 기록한다.

 

코드

#include <vector>
#include <algorithm>

using namespace std;

bool Compare(int Left, int Right)
{
    return Left >= Right;
}

vector<int> solution(int k, vector<int> score) {
    vector<int> answer;
    vector<int> HallOfFame;
    
    size_t Limit = score.size();
    for(size_t IDX = 0; IDX < Limit; ++IDX)
    {
        //0. 초기에 k일까지는 모든 출연 가수의 점수가 명예의 전당에 오르게
        if(IDX <= (k - 1))
        {
            HallOfFame.push_back(score[IDX]);
        }
        else
        {
            //1. k번째 순위의 가수 점수보다 더 높으면 
            //1-1. 출연 가수의 점수가 명예의 전당에 오르게 되고
            //1-2. 기존의 k번째 순위의 점수는 명예의 전당에서 내려오게 됩니다.
            if(score[IDX] > HallOfFame[k - 1])
            {
                HallOfFame.insert(HallOfFame.begin() + (k - 1), score[IDX]);
                HallOfFame.erase(HallOfFame.begin() + k);                
            }
        }
        
        // 명예의 전당 정렬
        sort(HallOfFame.begin(), HallOfFame.end(), Compare);
        // 꼴찌를 answer에 기록
        answer.push_back(HallOfFame.back());
    }    
    
    return answer;
}

 

 

회고

1. greater<int>()를 헷갈려서 Compare 함수를 정의해서 풀었다. 아쉬운 부분
2. 풀어보니 테스트 케이스에서 틀려서 왜인지 찾다보니 k일이 1부터 시작하는 것을 확인했고 이를 수정해서 풀었다.

 

다른 사람의 풀이

1. 벡터를 2개 정의하는 건 동일하지만 다른점은 "점수를 넣고 정렬하여 k보다 크면 나머지는 버린다.", "명예의 전당 마지막 점수를 집어넣는다."가 달랐다.
2. 우선순위 큐를 이용해 정렬을 자동화하고 큐의 첫 번째를 꼴등으로 집어넣는다.