프로그래머스 - H-Index

programmers.co.kr/learn/courses/30/lessons/42747#

코딩테스트 연습 - H-Index

 

citations 의 최대 길이가 1,000 이므로, O(N^2) 이 가능하다.

먼저 인용횟수와 비교할 수 있도록 sort() 함수로, 오름차순 정렬해준다.

문제에서 제시한 h 가 아래 코드에선 변수 i 와 같다.

i 보다 크거나 같은 citations[j] 값이 있으면 cnt++ 하여 카운팅 횟수를 늘린다

(변수 cnt 는 h 번 이상 인용된 논문의 갯수를 의미한다)

배열 전체를 다 돈 후, cnt 보다 i 값이 더 크면, 최대 h 보다 하나 더 큰 값이란 뜻이므로 answer = i - 1 을 부여한다.

주의할점은, n 만큼 인용횟수를 다 돌았는데, 문제 없이 전체를 다 순회 했을때이다.

즉, h 와 n 이 같을 때이다. 이 경우는 변수 i 가 n 보다 커졌을때 이므로, 

if (i > citations.size()) 만 잘 넣어서 처리하면 된다 (이 조건문을 안넣으면 테스트케이스 9 통과가 안됨)

 

- c++

 

#include <bits/stdc++.h>
 
using namespace std;
 
int solution(vector<int> citations) {
    int answer = 0;
    
    sort(citations.begin(), citations.end());
    
    int i;
    for (i = 1; i <= citations.size(); ++i) { // 인용횟수
        int cnt = 0;
        for (int j = 0; j < citations.size(); ++j) { // 선형 탐색
            if (citations[j] >= i) cnt++;
        }
        if (cnt < i) {
            answer = i - 1;
            flag = true;
            break;
        }
    }
    
    if (i > citations.size()) answer = citations.size();
 
    return answer;
}