정렬 - H-index

 

 

배열의 전체 크기가 1000 이하로 작기 때문에 시간복잡도를 O(n^2)으로 잡아도 매우 빠르게 통과가 가능했다.

 

 

import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

class Solution {
    public int solution(int[] citations) {
        int answer = 0;
        
        List<Integer> list = Arrays.stream(citations).boxed().collect(Collectors.toList());

        // 각 논문을 조회수 순으로 정렬
        Collections.sort(list, Collections.reverseOrder());
        
        // 모든 논문이 발행 편수 이상 인용이 되었는지 확인
        for (int h = 1; h <= list.size(); h++) {
            boolean isValid = true;
            for (int i=0; i<h; i++) {
                if (list.get(i) < h) {
                    isValid = false;
                    break;
                }
            }
            if (isValid && h > answer) {
                answer = h;
            }
        }
        
        return answer;
    }
}

 

 

 

 

다른 풀이를 보다가 개인적으로 인상 깊었던 풀이인데

 

인용 편수는 증가

인덱스는 감소

 

루프를 돌며 이 둘 간의 최소값만 체크해준 뒤

가장 큰 수를 리턴하면 된다.

누군지 몰라도 똑똑하네...

 

import java.util.*;

class Solution {
    public int solution(int[] citations) {
        Arrays.sort(citations);

        int max = 0;
        for(int i = citations.length-1; i > -1; i--){
            int min = (int)Math.min(citations[i], citations.length - i);
            if(max < min) max = min;
        }

        return max;
    }
}