프로그래머스 - H-Index - 정렬 - Java

1. 문제

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

2. 풀이

가장 큰 값부터 h의 조건을 만족하는지 검사해 나가며 가장 먼저 발견하는 값을 반환하면 된다.

예시에서 h는 0~5까지가 된다.(h편 이상이여야 하기 때문)
0 1 3 5 6으로 정렬되어있으면 h = 5일때 5번 이상 인용된 논문이 5편 이상이여야 한다.

즉 큰거부터 나열했을때 의 5번째의 array값이 5 이상이면 되는것이다.
즉 h = 5이면 citations[0]이 5이상인지 확인하는 것이다.
이는

citations[citations.length - i] >= i

로 표현될 수 있다.

가장 큰 값이 정답이니 같은 값을 찾으면 break문을 탈출한다.

3. 전체 코드

import java.util.*;

class Solution {
    public int solution(int[] citations) {
        int answer = 0;
        
        Arrays.sort(citations);
        
        for(int i = citations.length; i > 0; i--){
            if(citations[citations.length - i] >= i){
                answer = i;
                break;
            }
        }
        return answer;
    }
}

🥲이분탐색 풀이...

정렬 후 start = 0 / end = citations[N-1]로 잡고.....
이분탐색으로 풀었다. 이렇게 풀 필요가 없었잖아..!

import java.util.*;

class Solution {
    public int solution(int[] citations) {
        int N = citations.length;
        
        Arrays.sort(citations);
        
        int start = 0;
        int end = citations[N-1];
        
        if(end == 0) return 0;
        
        while(start < end){
            int mid = (start + end) / 2;
            int count = 0;
            for(int i = 0; i < N; i++){
                if(citations[i] >= mid) count++;
            }
            
            if(mid > count) end = mid;
            else start = mid + 1;
        }
        return end - 1;
    }
}