[프로그래머스] H-Index

programmers.co.kr/learn/courses/30/lessons/42747

코딩테스트 연습 - H-Index

 

문제는 위와 같으며 처음에는 문제를 잘 못 이해해서 어렵게 고민했던 것 같습니다... ㅠㅠ

 

이 문제는 정렬 카테고리였기 때문에 먼저 배열을 정렬한 다음 중간 인덱스를 찾아 인용된 횟수와 비교하는 식으로 문제를 해결하려고 하였습니다. 하지만 {12, 13, 14, 15} 의 경우 h 인덱스는 4로 인용 횟수와 상관없이 논문의 수와 관련이 있다는 것을 알게 되었습니다.

 

따라서 배열을 정렬한 다음 뒤에서부터 차례로 검사하면서 논문의 인용 횟수가 h 인덱스(answer)를 초과하는 경우 h 인덱스를 증가시키는 방식으로 문제를 해결할 수 있었습니다. 만약 논문의 인용 횟수가 h 인덱스보다 작거나 같은 경우에는 h번 이상 이용된 논문에 포함될 수 없기 때문에 검사를 종료하도록 하였습니다.

 

예를 살펴보면 다음과 같습니다. 주어진 논문이 [3, 0, 6, 1, 5] 이라고 하면 먼저 정렬을 한 뒤 아래 그림과 같은 과정을 거칩니다.

배열의 뒤에서부터 하나씩 h값과 인용횟수를 비교하여 인용횟수가 더 큰 경우 h번 이상 이용된 논문이 h개 이상이 되므로 h를 증가시키고 다시 앞에 있는 값을 확인합니다. 만약 h값보다 인용횟수가 같거나 작아지는 경우에는 h번 이상 인용된 논문에 포함될 수 없기 떄문에 (같은 경우에는 계속 검사를 해봐도 h번 이상 인용된 논문이 h개 이상이라는 조건을 만족하므로) 검사를 종료하고 지금까지 구한 h 값을 답으로 반환하면 됩니다.

 

import java.util.Arrays;

class Solution {
    public int solution(int[] citations) {
        int answer = 0;
        Arrays.sort(citations);  // 우선 정렬하기 (오름차순)
        for (int i = citations.length - 1; i >= 0; i--) {
            // 인용된 값이 h번 이상인 경우
            if (citations[i] > answer) {
                answer++;  // h 증가시키기
            } else {  // 그렇지 않은 경우는 더 이상 h개 이상으로 인용될 수 없으므로
                break;  // 반복 종료
            }
        }
        return answer;
    }
}