[프로그래머스/C++] 명예의 전당 (Lv.1)

링크: https://school.programmers.co.kr/learn/courses/30/lessons/138477?language=cpp

프로그래머스

 

1. 문제 접근

이 문제는 매일 새로운 점수가 들어올 때마다 상위 k개의 점수만 유지하고, 그중 가장 낮은 점수를 정답 배열에 저장하는 문제이다.

<핵심>
현재까지 나온 점수 중 상위 k개만 남긴다.
그중 최하위 점수를 answer에 넣는다.

- 따라서 점수를 저장할 벡터를 하나 만들고, 매번 정렬해서 상위 k개만 관리하면 된다.

 

2. 풀이(2개)

• 1번 풀이
  - 첫 번째 풀이는 매일 점수를 벡터에 넣고, 내림차순 정렬한 뒤 k개를 초과하면 가장 낮은 점수를 제거하는 방식이다.
  

  #include <string>
  #include <vector>
  #include <algorithm>
  
  using namespace std;
  
  vector<int> solution(int k, vector<int> score) {
      vector<int> answer;
      vector<int> my;
  
      for(int i = 0; i < score.size(); i++) {
          my.push_back(score[i]); // 매일 점수를 벡터에 넣고
          sort(my.begin(), my.end(), greater<int>()); // 내림차순 정렬
  
          if(my.size() > k) { // k개 초과하면
              my.pop_back(); // 가장 낮은점수 제거
          }
  
          answer.push_back(my.back());
      }
  
      return answer;
  }

• 2번 풀이
  - 두 번째 풀이는 벡터의 크기를 처음부터 최대 k개까지만 유지하는 방식이다.
  

  #include <string>
  #include <vector>
  #include <algorithm>
  
  using namespace std;
  
  vector<int> solution(int k, vector<int> score) {
      vector<int> answer;
      vector<int> temp;
  
      for(int i = 0; i < score.size(); i++) {
          if(temp.size() < k) { // 아직 점수가 k명으로 가득 차지 않았다면
              temp.push_back(score[i]); // 점수 추가
          }
  
          // k명 넘었고, 새로 오는 점수(score[i])가 > 최하위 점수(temp.back())보다 크다면,  
          else if(temp.back() < score[i]) { 
              temp.back() = score[i]; // 최하위 점수 새로오는 점수로 교채
          }
  
          sort(temp.begin(), temp.end(), greater<int>()); // 내림차순 정렬
          answer.push_back(temp.back()); // 가장 작은수 push_back
      }
  
      return answer;
  }

 

3. 문법

• pop_back()
  - 벡터의 마지막 원소를 제거하는 함수이다.
  

  vector<int> v = {100, 50, 10};
  
  v.pop_back();
  
  v = {100, 50}
  
  //1번 풀이 에서는 상위 k개를 초과했을 때 가장 낮은 점수를 제거하기 위해 사용했다.

 

4. 최종 요약

이 문제의 핵심은 상위 k개의 점수만 유지하는 것이다.

구분	설명
풀이 1	새 점수를 추가하고, 정렬 후 k개를 초과하면 제거
풀이 2	k개까지만 저장하고, 최하위 점수보다 큰 경우 교체
공통 핵심	내림차순 정렬 후 back()이 최하위 점수

 

풀이 1은 흐름이 직관적이다.

추가 → 정렬 → k개 초과 시 제거 → 최하위 점수 저장

 

 

풀이 2는 벡터 크기를 최대 k개로 유지한다.

k개 미만이면 추가
k개 이상이면 최하위 점수와 비교 후 교체

 

결국 두 풀이 모두 명예의 전당을 내림차순으로 관리하고, 매일 가장 낮은 점수를 정답 배열에 저장하는 방식이다.