1. 문제

난이도: Level 2
카테고리: 정렬

2. 풀이 방법

입력받은 배열에서 H개 이상 있는 값 H의 최댓값을 찾아야 한다.
이처럼 'n번 이상' 또는 '최댓값' 이라는 키워드를 보면 자연스럽게 정렬이 떠오른다.

내림차순으로 정렬해보면 그림이 잘 보인다.

• 내림차순 정렬 전
  • [3, 0, 6, 1, 5]
• 내림차순 정렬 후
  • [6, 5, 3, 1, 0]

입력받은 H 값, 즉, citations(index) 값 이상의 H는 index + 1개 만큼 있다.
그 다음 인덱스로 갈 수록 H 값이 작아지므로, 그 이상의 H의 개수도 증가한다.
따라서, citations(index) >= index + 1 의 경우 중 최댓값을 찾아야 한다.

2-1. sort 사용자 정의 비교 함수

3. 구현

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

using namespace std;

int solution(vector<int> citations) {
    int answer = 0;
    
    sort(citations.begin(), citations.end(), greater<int>()); // 내림차순 정렬
    
    for(int i = 0; i < citations.size(); i++){
        if (citations[i] >= i + 1){
            answer = i + 1;
        } else break; // 이외의 경우 break
    }
    
    return answer;
}

4. 느낀점

• (index + 1)은 arr[index] 이상 값이 몇 개 있는지를 나타낸다.
• 처음에는 오름차순 정렬을 해야 한다고 생각했다.
  예시가 잘 들어맞길래...
  생각해보면 h개 이상이어야 하므로 내림차순 정렬 후, 인덱스로 개수를 파악하는게 당연한 정답이었다.

• greater<>() 가 생각보다 런타임 에러 복병이었다.