문제 설명
"명예의 전당"이라는 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
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
'Code KATA > 알고리즘 코드카타' 카테고리의 다른 글
[2025.01.07] 모의고사 (0) | 2025.01.27 |
---|---|
[2025.01.24] 2016년 (1) | 2025.01.24 |
[2025.01.22] 콜라 문제 (0) | 2025.01.22 |
[2025.01.21] 푸드 파이트 대회 (0) | 2025.01.21 |
[2025.01.20] 가장 가까운 같은 글자 (0) | 2025.01.20 |