[Programmers / Sorting] - H Index C++ 풀이

---

 

프로그래머스 - 코딩테스트 고득점 키트

https://programmers.co.kr/learn/courses/30/lessons/42747

 

 

문제

 

 

 

풀이

 

해당 문제는 굉장히 복잡해보이지만 사실 간단한 규칙을 찾으면 풀 수 있다.

먼저 인용횟수를 내림차순으로 정렬한다.

 

그럼 예시로 주어진 벡터이 경우 6, 5, 3, 1, 0 순으로 정렬된다.

이 벡터를 탐색하면서 for loop를 돈다.

 

맨 앞에서부터 루프문을 돌며 

i = 0, citation 6 이상의 논문 1편 이상, 

i = 1, citation 5 이상의 논문 2편 이상,

i = 2, citation 3 이상의 논문 3편 이상,

i = 3, citation 1 이상의 논문 4편 이상, 

i = 4, citation 0 이상의 논문 5편 이상,

 

이 때 h의 최대값은 무엇일까, 바로 citations[i] 의 값이 i+1보다 작거나 같아지는 최초의 시점이다.

따라서 이를 코드로 구현하면 풀이가 가능하다.

 

코드

 

#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++;
    }
    return answer;
}

 

 

평가

 

규칙을 찾아내는 것이 다소 혼란스러울 수 있는 문제지만, 규칙만 찾아낸다면 구현 자체의 난이도는 높지 않은 문제이다.

정렬을 활용한 트릭문제는 대부분 규칙성을 빠르게 찾아야하기 때문에, 입력 예시값을 이리 저리 정렬해보면서 여러가지 풀이 방법을 고민하는것이 좋다.