[알고리즘 문제풀이] 프로그래머스 H-Index

어제 그저께 공부를 많이 못 했다 ! ㅠㅡㅠ 그저께는 친구의 꼬임에 넘어가.. 공부를 더 해야하는데 맥주를 먹으러 갔고.. 어제는 저녁 약속이 있었는데 낮에는 학교 과제를 하느라 다 보내버렸다 + 수업 꽉 찬 목요일.. 더 부지런하게 보내지 못했음을 반성하며,,..

오늘 푼 문제는 프로그래머스 고득점 kit 정렬 분류의 level2 문제이다 ! ( 문제 링크 )

문제 설명

H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다.

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

어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요.

나머지 논문이 h번 이하 인용되었다면
이 문장에 대해서 질문에 말이 많았다. 사실 굳이 없어도 되는 문장이 맞다 ! h번 이상 인용된 논문이 h개라면 나머지는 당연히 h이하도 아닌 미만일테니,, 내 생각에는 이 문장은 그냥 정렬해서 푼다면 그 이전의 값들은 다 h이하로 인용된 논문들이 되므로, 정렬 문제라서 넣어놓은 문장인 것 같다.

제한 사항

• 과학자가 발표한 논문의 수는 1편 이상 1,000편 이하입니다.
• 논문별 인용 횟수는 0회 이상 10,000회 이하입니다.

입출력 예

풀이 방법

처음 문제를 읽고는 정렬을 해서 풀이의 효율성을 높이긴 하겠지만, 정렬 외에 문제 풀이 방법을 고민했다. 또한 h가 꼭 리스트에 있는 인용 횟수는 아닐 수도 있겠구나 생각했다. ( 문제에 이런 부분이 명시되어 있지는 않았으나 문제를 읽으며 파악해야 하는 부분 ! )

처음에는 어떠한 인용횟수 h를 찾아야하는 문제이기 때문에 이분 탐색으로 풀 수 있겠다는 생각을 했다. 하지만 설계를 하다보니 이분 탐색으로 푼다면 mid보다 큰 횟수로 인용된 논문의 수를 받아오기 위해서 오히려 시간 복잡도가 올라갈 수 있겠다는 생각을 했다. 심지어 문제 제한에서 배열 사이즈의 범위가 크지 않았다 !

그래서 그냥 정렬 후 한 번의 반복을 통해서 답을 구해내기로 했다. 결국 답이 있는 범위는 인용된 수(citations[i])와 그 보다 많은 횟수 인용된 논문의 수(citations.length-(i+1))의 크고 작음이 바뀌는 경계이다.

즉 위의 그림에서 3까지는 3번 이상 인용된 논문의 수가 3보다 크다. 하지만 5부터는 5번 이상 인용된 논문의 수가 5개가 되지 않는다. 이 경우에 3이 h가 아니라면, 5부터는 h가 될 수 없으므로, 3 뒤에 있는 [5,6,7,9]의 길이가 h가 될 수 있는 가장 큰 값인 것이다 !

즉 정렬된 배열을 순차적으로 탐색하며, 저 경계를 찾는다. 나는 h가 될 수 없는 값을 기준으로 찾았다. (위의 그림 예시에서 3이 아닌 5를 찾은 것) 그러므로 찾은 값부터 원소의 개수와 직전 원소의 값을 비교해서 더 큰 값을 반환해주었다.

이 때, 첫 번째 원소부터 h가 될 수 없는 값일 수 있으므로, 매번 조건문을 다는 것 보다 try-catch문에서 값을 넣어주면 되겠다 싶어서 그렇게 처리해주었다.

코드

import java.util.Arrays;
class Solution {
    public int solution(int[] citations) {
        int answer = 0;
        Arrays.sort(citations);
        int temp;
        for(int i=0; i<citations.length; i++){
            if((citations.length-i) < citations[i]){
                try{ temp = citations[i-1]; }catch (Exception e){ temp = 0; }
                answer = Math.max((citations.length-i), temp);
                break;
            }
        }
        return answer;
    }
}