[2025.01.23] 명예의 전당 (1)

문제 설명

"명예의 전당"이라는 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 함수를 완성해주세요.

 

 

제한사항

• 3<=k<=100
• 7<=score의 길이<=1,000
  • 0<=score[i]<=2,000

 

 

입출력 예

k			score	result	설명
3			[10, 100, 20, 150, 1, 100, 200]	[10, 10, 10, 20, 20, 100, 100]	문제의 예시와 같습니다.
4			[0, 300, 40, 300, 20, 70, 150, 50, 500, 1000]	[0, 0, 0, 0, 20, 40, 70, 70, 150, 300]	아래와 같이 [0, 0, 0, 0, 20, 40, 70, 70, 150, 300]을 return 합니다.

 

 

문제 풀이

풀이 언어 : C++

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

// 내림차순 비교
bool compare(int a, int b)
{
    return a>b;
}

vector<int> solution(int k, vector<int> score) {
    vector<int> answer;
    for(int i=0; i<score.size(); i++)
    {
        sort(score.begin(), score.begin()+i+1, compare); // 0~i번째까지 내림차순 정렬
        
        if(i<k) // k명의 참가자가 아직 나오지 않았을 때
        {
            answer.push_back(score[i]); // i번째 참가자 점수 저장
        }
        else // k명 이상의 참가자가 되었을 때
        {
            answer.push_back(score[k-1]); // k번째 참가자 점수 저장
        }
    }
    return answer;
}

배열에서 k번째로 큰수를 구하는 방법은 배열을 정렬한 후 k+1번째 수를 가져오는 것이다. 이걸 계속 반복하면서 k+1번째 수를 가져오면 되는 것이다.

 

반복문을 이용해 점점 방송의 일자를 늘려간다. 그리고 그 안에서는 0부터 방송일자까지의 배열 요소를 정렬한다. score.begin()이 첫 방송의 점수일 것이고 score.begin()+i가 i일째 방송에서 나온 점수일 것이다. 하지만 sort 함수는 마지막은 포함하지 않고 정렬하기 때문에 거기에 +1을 해준다.

 

이렇게 일부 정렬된 벡터를 이용해서 이제 명예의 전당에서 꼴찌를 찾아내면 된다. k일 까지는 모든 참가자가 명예의 전당에 올라가 있다. 따라서 그냥 그 범위에서 꼴찌를 고르기만 하면 된다. i번째 점수까지 정렬을 마쳤다면 i번째 사람이 명예의 전당의 꼴찌인 것이다. 따라서 i<k일 때 명예의 전당은 score[i]가 된다. 하지만 k일 이후부터는 k번째 참가자를 찾아야 한다. 따라서 score[k-1]의 점수를 저장한다.

 

 

오답 노트

sort 함수는 끝 수는 빼고 정렬한다는 것을 잊고 그냥 score.begin()+i만 적었다가 다른 결과가 나와 실패하였다.

k번째 참가자 점수를 저장하려는데 그냥 score[k]를 저장하였다가 다른 결과가 나와 실패하였다. k가 3이면 3번째로 점수가 큰 사람을 원하는 것이므로 결국 인덱스는 2인 점수를 찾아와야 하는 것이다.

 

 

문제 링크

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

프로그래머스