[프로그래머스/Java] H-Index(정렬 문제)

프로그래머스 알고리즘 고득점 Kit의 정렬 파트 문제 중 하나인 H-Index를 자바로 풀어보았다. 

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

프로그래머스

 

 

 처음에는 너무 간단해 보여서 쉽게 풀겠구나 하고 접근하여 제출했다. 하지만 생각보다 신경 써야 할 조건이나 반례가 많았다. 처음에는 그냥 정렬해 준 후, if(i+1 >= cites[i]) 조건만 충족하면 되는 거 아닌가?라고 생각해서 그렇게 코드를 작성했다. 

 그리고 만난 반례가 [11, 10, 1] 이었다. 내가 한 논리대로라면 1이 답이 되는데, 사실 답은 2이다. 즉, cites 배열 내에 속한 숫자가 아니라도 답이 될 수 있는 것이다.

 그리고 다른 예외는 또 있다. 끝까지 (i+1 >= cites[i])가 충족되는 cites 내 요소가 나오지 않는 경우이다. 이 경우는 그냥 단순히 array의 길이를 리턴해주면 된다. 

import java.util.*;

class Solution {
    public int solution(int[] citations) {
        Integer[] cites = Arrays.stream(citations)
            .boxed()
            .toArray(Integer[]::new);
        Arrays.sort(cites, Collections.reverseOrder());
        
        int len = cites.length;
        int i;
        for (i = 0; i < len; i++) {
            if (i+1 >= cites[i]) break;
        }
        
        int answer;
        if (i == len) answer = len;
        else if (i > 0 && cites[i] < i) {
            answer = i;
            while (answer < cites[i-1] && answer < i) answer++;
        } else answer = cites[i];
        return answer;
    }
}

 

 

 이렇게 풀고 난 후, 더 간단히 푸는 방법이 없을까 하고 다른 사람들의 풀이를 보다가, 단순한 논리를 사용하는 방법을 찾았다. 그래서 거기에서 인사이트를 찾아 코드를 다시 작성해 보았다. 아래처럼 정말 간단한 코드로 문제를 해결할 수 있다.

 문제의 핵심은 문제의 말 속에 있었다. 논문 n편 중, h번 이상 인용된 논문이 h 편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index이다. 따라서, 만약 현재 탐색 중인 논문의 인용 횟수가 3번이고, 3번 이상 인용된 논문이 5편이다. 그럼 H-Index는 3이 될 것이다. 만약 현재 탐색 중인 논문의 인용 횟수가 5번이고, 5번 이상 인용된 논문이 3편이다. 그럼 H-Index는 다시 3이 될 것이다. 핵심은 '이상'이라는 말에 있다. h보다 같거나 큰 모든 범위가 포함 대상이므로, 더 작은 수가 h에 해당되어야 하는 것이다. 따라서, 현재 탐색 중인 논문의 인용횟수(citation[i])와 그 이상 인용된 논문(len-i)를 비교하여 더 작은 값을 찾는다. 그리고 우리가 찾아야 하는 값인 h의 최댓값이니, 이 중 최댓값을 찾아주면, 우리가 찾고자 하는 값이 되는 것이다. 

import java.util.*;

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