< 프로그래머스 C++ > 명예의 전당(1)

 

문제 설명

매일 1명의 가수가 점수를 받는데, 이 점수가 지금까지 출연한 가수들 중 상위 k등 안에 들면 명예의 전당에 오른다

매일 명예의 전당 목록의 최하위 점수를 발표해야 하고, 1일부터 마지막 날까지의 발표 점수를 vector로 반환하면 되는 문제다

예시

k = 3, score = [10, 100, 20, 150, 1, 100, 200]

 

answer = {10, 10, 10, 20, 20, 100, 100}

score	10	100	20	150	1	100	200
명예의 전당 (k=3)	10	100, 10	100, 20, 10	150, 100, 20	150, 100, 20	150, 100, 100	200, 150, 100
발표 점수	10	10	10	20	20	100	100

 

---

문제 해석

매일 새로운 점수가 들어올 때마다 상위 k개를 유지하고, 그 중 가장 낮은 점수를 발표하면 된다

• 점수를 추가하고 정렬한 뒤
• k개를 초과하면 가장 낮은 점수를 빼고
• 남은 것 중 마지막(최하위)을 발표 점수에 넣으면 끝

---

문제 풀이

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> solution(int k, vector<int> score) {
    vector<int> answer;
    vector<int> arr;

    for(int i = 0; i < score.size(); ++i)
    {
        arr.push_back(score[i]);
        sort(arr.begin(), arr.end(), greater<>());  // 내림차순 정렬

        if(arr.size() > k)
            arr.pop_back();  // k개 초과 시 가장 작은 점수 제거

        answer.push_back(arr.back());  // 현재 최하위 점수 발표
    }

    return answer;
}

---

핵심 포인트

1. arr 크기를 k개로 유지

매번 정렬하고 k개만 남기는 방식을 선택했다

arr.push_back(score[i]);                    // 점수 추가
sort(arr.begin(), arr.end(), greater<>());  // 내림차순 정렬
if(arr.size() > k) arr.pop_back();          // 초과분 제거

내림차순 정렬을 했기 때문에 마지막 원소가 항상 최하위 점수가 된다
그래서 매일 발표 점수를 구할 때 arr.back()만 쓰면 된다

2. greater<>()로 내림차순 정렬

처음엔 람다를 사용했는데, 람다 대신 greater<>()를 쓰면 한 줄로 끝난다

sort(arr.begin(), arr.end(), greater<>());

// 람다로 쓰면 이런 식
sort(arr.begin(), arr.end(), [](int a, int b){ return a > b; });

 

3. arr.back()과 arr.end()의 차이

처음에 헷갈리기 쉬운 부분이다

arr.back()	마지막 원소의 값	실제 데이터를 가져옴
arr.end()	마지막 다음 위치 iterator	끝을 표시하는 마커

값을 꺼내고 싶을 땐 back()을 쓰면 되고, end()는 주로 반복문이나 알고리즘 함수의 끝 위치 표시에 쓰인다

 

4. k일 이전도 같은 로직으로 처리됨

처음엔 "k일까지는 모든 점수가 명예의 전당에 오른다"는 조건 때문에 분기처리가 필요하다

• 첫날: arr = [10] → size 1, k=3보다 작으니 그대로 유지 → back() = 10
• 둘째날: arr = [100, 10] → size = 2, 그대로 유지 → back() = 10
• 셋째날: arr = [100, 20, 10] → size = 3, 그대로 유지 → back() = 10
• 넷째날부터 size = 4가 되어 pop_back 발동

별도 분기 없이도 자연스럽게 동작하는 게 이 풀이의 매력

---

트러블슈팅

arr.back()과 arr.end()를 헷갈렸던 문제

처음 코드를 짤 때 vector의 마지막 값을 꺼내려고 arr.end()를 사용했다

 

answer.push_back(arr.end());

 

end()가 마지막 원소를 반환한다고 잘못 알고 있었다

찾아보니 end()는 마지막 원소의 다음 위치를 가리키는 iterator고, 값을 꺼내는 함수가 아니었다
주로 반복문 종료 조건이나 알고리즘 함수의 끝 위치를 표시할 때 쓰인다

함수반환값설명

arr.back()	마지막 원소의 값	실제 데이터를 꺼낼 때 사용
arr.end()	마지막 다음 위치 iterator	끝을 표시하는 마커, 값이 아님

해결 방법

값을 꺼내야 하니 back()을 써야 했다

answer.push_back(arr.back());

vector에서 첫 원소나 마지막 원소를 직접 꺼낼 땐 front(), back()을 쓰고, iterator가 필요한 경우엔 begin(), end()를 쓴다는 걸 확실히 정리할 수 있었다