[프로그래머스/Lv.2] H-Index - Java

문제

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

프로그래머스

---

리뷰

프로그래머스 코딩테스트 고득점 Kit에서 정렬로 분류되어 있는 문제이다. 아주 쉬워 보이지만 질문하기에서 각종 테스트케이스를 긁어 모으고 나서야 해결할 수 있었다.

 

문제를 처음 봤을 땐 "뭔 소리야?"
좀 읽어 보고 나선 "아 알겠다."(아니었음)
문제를 푼 다음엔 "왜 안 되지?" × ∞

충격적인 첫 채점 결과

 

실패 원인이 되었던 문제의 중요한 포인트들을 짚어 보자면 아래와 같다.

1. H-Index가 배열 citations에 있는 값이 아닐 수도 있다.
   • citations의 두 값 사이에 있는 정수일 수도 있다.
   • 심지어 citations의 최솟값보다 작을 수도 있다.
2. 배열 citations에 중복값이 있을 수 있다.
   • 이 경우, h번 이상 인용된 논문이 아닌 나머지 논문에서 인용횟수가 중복인 논문들을 제외하고 인용횟수를 계산해야 한다.

 

---

풀이

H-index는 문제에 주어진 조건을 충족하는 수 중 '최댓값'이므로, 먼저 citations를 정렬한 후 마지막 원소부터 판단한다.

1. h번 이상 인용된 논문의 수는 [n-(현재 판단하는 원소의 인덱스)]개이다.
2. 현재 원소의 값보다 작은 값들을 모두 더한 값과 현재 원소의 값을 비교한다. 이 때 중복값이 있을 수 있으므로, 단순히 현재 원소의 인덱스 앞의 원소들을 슬라이싱해서 더하면 안 된다.

그런데 정답이 citations 안에 있는 값이 아닐 수도 있다. 그래서 현재 원소와 이전에 판단했던 원소(즉, 배열 상 다음 위치에 있는 원소) 사이의 값들에 대해 위 조건을 충족시키는지 한 번 더 판단했다.

 

이렇게 조건을 충족하는 값이 있으면 그 값을 answer에 넣고 반복문을 탈출한다.

 

그런데 answer이 초깃값에서 달라지지 않았다면, citations의 최솟값보다도 H-Index가 작다는 것을 의미한다. 그래서 0부터 citations의 최솟값(citations[0]) 사이에 있는 수들에 대해 위 조건을 충족시키는지 판단해야 한다.

 

---

코드

import java.util.Arrays;

class Solution {
    public int solution(int[] citations) {
        int answer = -1;
        
        int n = citations.length;
        Arrays.sort(citations);
                
        for(int i=n-1;i>=0;i--){
            int cur = citations[i];
            
            // cur보다 작은 값 중 최댓값의 인덱스를 저장함
            int lessMax = 0;	
            for(int j=i-1;j>=0;j--){
                if (citations[j]<cur){
                    lessMax = j;
                }
            }
            
            // 0~lessMax 인덱스에 있는 값들의 합
            int[] lessH = Arrays.copyOfRange(citations, 0, lessMax+1);
            int totalLessH = total(lessH);
            
            // citations 안에 있는 값에 대해 H-Index 조건 판단
            if(totalLessH<=cur && n-i >=cur){
                answer = cur;
                // citations 안에 있지 않은 값에 대해 H-Index 조건 판단
                if (i<n-1){
                    for(int j=citations[i+1]-1;j>cur;j--){
                        if(totalLessH<=j && n-i-1 >=j){
                            answer = j;
                            break;
                        }
                    }
                }
                break;
            }
        }
        
        // citations 최솟값보다도 H-Index가 작은 경우 판단
        if(answer<0){
            for(int j=citations[0]-1;j>=0;j--){
                if(n >=j){
                    answer = j;
                    return answer;
                }
            }
        }
        return answer;
    }
    
    // 배열에 있는 수를 모두 더하는 함수
    private int total(int[] arr){
        int result = 0;
        for(int num:arr){
            result+=num;
        }
        
        return result;
    }
}