H-index

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

프로그래머스 정렬 문제 중 H-index를 이중 포문으로 풀고 난 후 최적화된 코드가 무엇일까 찾아보다가 놀라서 글을 쓰게 됐다.

나를 놀라게 한 아이디어

어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다.

1. 이 문장에서 h의 최댓값은 n이 된다는 사실을 먼저 알아야 한다. (나는 이 조건도 생각하지 않고 풀었다)

2. 그리고나서 정렬한 citations에서 두 값 citations[i], citations.length-i에서 i를 증가시키며 값의 비교를 반복하는데 citations[i] >= citations.length-i 일 때의 citations.length-i의 값이 답이 된다.

i값이 증가 할수록 논문 인용 횟수가 증가한다는 점과 가능한 최대 논문 개수가 줄어든다는 점을 이용한 것인데 교차점이 최댓값이라는게 너무 신기했다. 이게.. 사고력..? 🤭

import java.util.*;

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

---

엄청난 영감을 준 블로그
https://bada744.tistory.com/94 (프로그래머스/level2 H-index _ willcometrue)

틀린 개념이나 의문점이 있을 시 편하게 댓글 달아주시면 감사하겠습니다 :)