정렬 (H-index)

프로그래머스 알고리즘 고득점 문제 중 Level 2
H-index 문제

📘 H-index 공식

1. 연구자가 발표한 논문들(배열)을 인용 횟수에 따라 내림차순 or 오름차순 정렬
2. 인용 횟수와 순위를 비교
3. 인용 횟수가 순위보다 크거나 같은지(>=) 확인
4. h번째 논문의 인용횟수가 h번 이상이면, 그 연구자의 H-index는 h로 설정

📑 나의 풀이 (int 배열 이용)

import java.util.Arrays;

class Solution {
    public int solution(int[] citations) {
        int answer = 0;
        int j = 0;
        
        // 오름차순 정렬
        Arrays.sort(citations);
        
        // H-index 값 계산 
        for(int i=citations.length-1;i>=0;i--){
            if(citations[i]>=j+1){
                answer++;
            }
            j++;
        }
        return answer;
    }
}

먼저, Arrays.sort() 메소드는 기본적으로 오름차순 정렬이며, int는 primitive type(원시타입)이라 comparaotr 같은 객체 기반 메소드가 적용되지 않기 때문에, 내림차순 정렬 후, 뒤에 인덱스부터 뒷 순위와 하나씩 비교하여 H-index를 구함.

📑 나의 풀이 (Integer 객체 배열 이용)

import java.util.*;

class Solution {
    public int solution(int[] citations) {
        int answer = 0;
        
        // Integer 객체 배열로 변환
        Integer[] arr = new Integer[citations.length];
        
        for(int i=0;i<citations.length;i++){
            arr[i] = citations[i];
        }
        
        // 내림차순 정렬
        Arrays.sort(arr, Comparator.reverseOrder());
        
        // H-index 계산
        for(int i=0;i<arr.length;i++){
            if(arr[i]>=i+1){
                answer++;
            }else break;
        }
        return answer;
    }
}

내림차순 정렬을 사용해보기위해, Integer 객체 배열로 변환하여 다시 풀어보았다.
Integer 객체 배열을 사용했을 때는 기본형인 int를 객체로 감싸는 작업인 boxing과, 객체에서 기본형값을 꺼내는 unboxing 작업이 필요했다.

따라서, 이런 작업이 필요없는 int[] 배열을 사용했을 때, 속도와 메모리 측면에서 훨씬 효율적이었다.

Integer[] 배열을 사용하는 이유는 null값을 저장할 수 있기 때문에 값이 없거나 초기화되지 않은 상태를 표현하기위해서는 Integer[]를 사용해야한다.

❗❗ Comparator.reverseOrder() 와 collection.reverseOrder() 차이?

두 메소드 다 내림차순 정렬시 사용하지만,comparator.reverseOrder() 주로 배열에 사용되며, collection.reverseOrder()는 리스트에서 주로 사용된다.

👀 문제 출처