프로그래머스 - H-Index

프로그래머스 - H-Index

카카오 문제 풀다가 머리아파서 쉴겸 풀었는데, 다 풀고 다른 사람 코드를 보는데 신박한 풀이가 있어서 놀랐다.

일단 정렬 카테고리답게 내림차순으로 정렬한 뒤 i번째 element의 크기가 i + 1보다 작아질 때 i를 반환해주면 정답이다.
예를 들어, [6, 5, 3, 1, 0]의 경우
i = 0에서 1 <= 6 이니 다음으로 넘어가고,
i = 1에서 2 <= 5 이니 다음으로 넘어가고,
i = 2에서 3 <= 3 이니 다음으로 넘어가고,
i = 3에서 4 > 1 이니 3을 반환해주면 된다.

즉, i+1이 의미하는 것은 현재까지 논문의 수를 의미한다.
내림차순으로 정렬했기 때문에 현재까지 논문의 수가 citations보다 작은 경우엔 H-Index로 설정하기엔 크기 때문에, citations이 더 작아지는 경우까지 논문 갯수를 세주면 된다.
citations[i]가 현재까지 논문의 수보다 작아지면 바로 정답을 리턴해주면 된다. (첫 번째 코드)

만약 이걸 생각하지 못하더라도 가장 많이 인용된 citations[k] 값부터 0까지 citations을 순회하면서 풀어도 된다. (두 번째 코드)

난 처음에 첫 번째 풀이로 시도하다가 부등호 실수를 해서 일단 두 번째로 풀고, 다시 첫 번째로 풀었는데, 다른 사람의 코드를 보니 바이너리 서치로 푼 사람도 있어서 따라해봤다.

mid 값이 현재 H-Index라고 생각하고, citations을 순회하면서 mid값 이상인 원소 갯수가 mid 이상이면 H-Index로 설정이 가능한 경우이기 때문에 left를 mid로 설정해준다.
만약 mid값 이상인 원소의 갯수가 mid 미만이라면 현재 H-Index(mid) 값이 너무 큰 것이기 때문에 right를 mid로 설정하고 다음 바이너리 서치로 진행하면 된다.

첫 번째 코드의 경우 정렬 오버헤드 때문에 O(NlogN)일 것이고, 두 번째는 O(NlogN)이어도, O(N^2)에 가까운 굉장히 느린 코드이다.
세 번째는 바이너리 서치로 풀 수 있기 때문에 O(N)정도에 가까운 O(NlogN)이 된다. (바이너리 서치 발생 횟수를 상수로 판단하면 O(N)이라 생각해도 될듯.)

실제로 결과도 바이너리 서치가 가장 빠르고, 일일히 비교하는 코드가 제일 느리다.

int solution(vector<int> citations) {
    int answer = 0;
    sort(citations.begin(), citations.end(), greater<>());
    int size = citations.size();
    int max_element = citations[0];
    
    for(int i=0;i<size;i++) 
        if(i + 1 > citations[i]) 
            return i;
        
    return size;
}

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

using namespace std;

int solution(vector<int> citations) {
    int answer = 0;
    int size = citations.size();
    sort(citations.begin(), citations.end(), greater<>());
    int max_value = citations[0];
    for(int i=max_value;i>0;i--) {
        int cnt = 0;
        for(int j=0;j<size;j++) {
            if(citations[j] < i)
                break;
            cnt++;
        }
        if(cnt >= i) {
            answer = i;
            break;
        }
    }
    return answer;
}

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

using namespace std;

bool binary(const vector<int> &citations, const int &size, int mid)
{
    int cnt = 0;
    for(int i=0;i<size;i++) 
        if(citations[i] >= mid)
            cnt++;
    
    return cnt >= mid;
}

int solution(vector<int> citations) {
    int answer = 0;
    int size = citations.size();
    
    int left = 0;
    int right = 1 << 14;
    
    while(left + 1 < right) {
        int mid = (left + right) / 2;
        
        if(binary(citations, size, mid)) {
            answer = mid;
            left = mid;
        } else 
            right = mid;
    }
    return answer;
}