[LV.2][JAVA] H-Index

https://school.programmers.co.kr/learn/challenges?tab=algorithm_practice_kit

프로그래머스

푸는 동안 사고과정 및 개선점

처음에 문제를 읽고 너무 단순하다고 생각했다.

import java.util.*;

class Solution {
    public int solution(int[] citations) {
        int answer = 0;
        Arrays.sort(citations);
        int len = citations.length;
        for(int i=0; i<len; i++){
            int tmpH = citations[i];
            // 현재 위치 포함해서 남은 논문 편 수
            int left = len - i;
            if(tmpH > left){
                break;
            }else{
                answer = tmpH;
            }
        }
            
        return answer;
    }
}

정렬해서, 처음부터 각 원소를 돌면서 남은 논문 편수를 비교해 종료조건을 설정해주면 되는 게 아닌가? 라고 생각했다.

이러면 문제가, 모든 논문의 인용횟수가 len 보다 크다면 바로 끝나버린다. 그리고 H-index의 정의를 제대로 반영하지 못했다.

"h번 이상 인용된 논문이 h편 이상"이라는 문장이 그건데, 나는 현재 인용된 논문 횟수와 단순히 남은 논문 수를 기준으로 비교하고 있어서 틀린 답이 나올 수 밖에 없다.

인용횟수가 중심이 아니라, 증가하는 H-index에 맞는 인용 조건을 찾는게 문제 해답이었다.

import java.util.*;

class Solution {
    public int solution(int[] citations) {
        int answer = 0;
        ArrayList<Integer> arr = new ArrayList();
        for(int c: citations){
            arr.add(c);
        }
        arr.sort(Collections.reverseOrder());

        int len = citations.length;
        for(int i=0; i<len; i++){
            int tmpH = arr.get(i);
            if (tmpH < i + 1) {
                break;
            } else {
                answer = i + 1;
            }
        }
        
        return answer;
    }
}

정렬 순서부터 바꿨다. 아예 인용횟수가 많은 논문 부터 보게 하는 것이다.

종료 조건은 인용횟수가 h-index 후보 보다 작아질 때다. 이렇게 하면 i번째 논문을 확인할 때, 이미 i편의 논문이 현재 논문 이상으로 인용되었음을 알 수 있다. 오름차순 정렬을 해버리면 h-index 조건에 맞는 지 검증하는 로직이 하나 더 필요한데, 내림차순으로 하면 보장되어있어서 더 효율적이다.

 

조건이 단순했는데 말이 좀 모호하게 되어있어서 애먹었던 문제다. 처음 틀리고서 왜 틀렸는 지 감이 안잡혔다.

 

도움이 됐다면 댓글이나 공감 버튼 한 번씩 누르고 가주세요!