[프로그래머스] H-Index - Java

문제 설명

 

코딩테스트 연습 - H-Index

 

풀이 회고

우선 해당 문제는 문제를 잘못 이해함으로 인해 삽질하는 시간이 많았습니다. 문제에서 요구하는 것은 "논문 n편 중, h번 이상 인용된 논문이 h편 이상일 때 h의 최대값"을 구하는 것입니다. 이때 h라는 수의 범위는 무엇일까요? 저는 처음에 이 문제의 h라는 수가 매개변수(citations)로 주어진 배열에 존재하는 정수 중에 존재한다고 착각하고 있었습니다. 하지만 이에 대한 풀이를 확실하게 구해도 정답이 나오지 않았기에 무언가 잘못됐다고 생각이 들었습니다.

 

문제에서 명확하게 명시하지는 않았지만, h라는 수의 주어진 범위는 0 ~ 1000까지라고 볼 수 있습니다. 우선, 문제에서는 "제한사항"을 명기해주었는데 논문의 수는 1편 ~ 1000편까지이며, 논문별 인용 횟수는 0회 ~ 10000회입니다. 즉, 최악의 경우에서는 논문의 수가 1000편으로 논문별 인용 횟수가 모두 1000회 이상 넘는 경우인데 이럴 경우에 h라는 수는 최대 1000이 될 수 있는 것입니다.

 

이에 빠른 탐색을 위해 주어진 매개변수 정수형 배열(citations)을 오름차순으로 정렬했고, 이를 작은 숫자부터 순차 탐색하도록 했습니다. 탐색 시에는 h라는 숫자와 비교하여 h 이상이면 cnt++ 해주도록 했는데, 이는 "h편 이상"인 경우를 체크하기 위함이었습니다. 반복적인 cnt++을 통해 cnt가 h 이상이되면 해당 h 수는 h-index라고 할 수 있는 것입니다. 다만, 문제에서 요구하는 것은 h-index의 최대값이므로 더 큰 h 수로 탐색시켜주었습니다.

 

이때 오름차순의 결과로 해당 배열(citations)에 마지막 원소는 최대값입니다. 즉, h라는 수가 이 수(배열 원소 중 최대값)보다도 크다면 h번 이상 인용된 논문이 없다는 것이므로 탐색할 필요가 없습니다. 그리하여 좀 더 빠른 탐색을 위해 break를 시켜주도록 했습니다.

 

 

소스 코드

import java.util.Arrays;

class Solution {
    public int solution(int[] citations) {
        int result = 0, cnt = 0, n = citations.length;

        Arrays.sort(citations);

        for (int h = 0; h < 1001; h++) {
            if (h > citations[n-1]) break;
            for (int citation : citations) {
                if (citation >= h) {
                    cnt++;
                }
                if (cnt >= h) {
                    result = h;
                    break;
                }
            }
            cnt = 0;
        }

        return result;
    }
}

 

 

참고자료

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