[정렬] 프로그래머스 - H-Index

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

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

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

 

제한사항

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

입출력 예
citations	return
[3, 0, 6, 1, 5]	3

 

입출력 예 설명

이 과학자가 발표한 논문의 수는 5편이고, 그중 3편의 논문은 3회 이상 인용되었습니다. 그리고 나머지 2편의 논문은 3회 이하 인용되었기 때문에 이 과학자의 H-Index는 3입니다.

---

풀이

import java.util.Arrays;
import java.util.Collections;

class Solution {
    public int solution(int[] citations) {
        int answer = 0;
        int arrSize = citations.length;
        
        // 기본형 배열을 정렬하기 위해 Integer 배열로 변환
        Integer[] objectArray = new Integer[arrSize]; 
        for (int i = 0; i < arrSize; i++) {
            objectArray[i] = citations[i]; // 기본형 값을 Integer로 변환하여 저장
        }
        
        // 내림차순 정렬
        Arrays.sort(objectArray, Collections.reverseOrder());
 
        // H-Index 계산
        for (int index = 0; index < arrSize; index++) {
            if (objectArray[index] >= index + 1) { // H-Index 조건
                answer = index + 1; // H-Index 값 업데이트
            } else {
                break; // 조건을 만족하지 않으면 더 이상 체크할 필요 없음
            }
        }
        
        return answer; // 최종 H-Index 값 반환
    }
}

 

배열 정렬

• 위 코드의 이전 단계에서 objectArray는 내림차순으로 정렬되어 있습니다. 즉, 가장 많이 인용된 논문이 배열의 첫 번째 요소에 위치하게 됩니다.
• 예를 들어, 인용 수가 [6, 5, 3, 1, 0]이라면, 정렬된 objectArray는 [6, 5, 3, 1, 0]가 됩니다.

인덱스와 H-Index 조건

• 루프는 정렬된 배열의 각 요소에 대해 반복합니다.
• index는 배열의 인덱스를 나타내고, index + 1은 현재 위치까지 고려한 "H-Index" 후보입니다. 즉, 인덱스가 0일 때는 H-Index가 최소 1이 될 수 있습니다.

H-Index 조건

• objectArray[index] >= index + 1: 이 조건은 "현재까지 인용된 논문 수가 현재 인덱스 값보다 같거나 커야 한다"는 것을 의미합니다.
  • 예시:
    • index = 0: objectArray[0] (6) >= 1 (index + 1) → true
    • index = 1: objectArray[1] (5) >= 2 (index + 1) → true
    • index = 2: objectArray[2] (3) >= 3 (index + 1) → true
    • index = 3: objectArray[3] (1) >= 4 (index + 1) → false
• H-Index는 "최소한 H회 인용된 논문이 H편 이상"인 최대 H 값을 찾아야 하므로, 조건이 참인 경우 H-Index를 업데이트합니다.

---

나는 쉽게 내림차순을 하기 위해(Collections.reverseOrder()사용하기 위해),

int[]에서, Integer[] 로 바꿔줬는데, 굳이 그렇게 하지 말고

직접 int[]배열에서 바로 내림차순 정렬을 해주는 게 성능, 메모리 상 더 좋다고 한다.

기본형 배열 vs 객체 배열

1. 기본형 배열:
   • 기본형 데이터 타입(예: int, char, double 등)의 배열입니다.
   • 예를 들어, int[]는 정수형 값을 저장하는 배열입니다.
   • 기본형 배열은 메모리에서 더 적은 공간을 차지하며 성능이 더 우수합니다.
    

    
2. 객체 배열:
   • 객체(예: Integer, String, Double 등)를 저장하는 배열입니다.
   • 예를 들어, Integer[]는 정수형 값을 Integer 객체로 저장하는 배열입니다.
   • 객체 배열은 기본형 배열에 비해 메모리 사용이 더 많고, 박싱과 언박싱으로 인해 성능이 떨어질 수 있습니다

Integer[] objectArray = {6, 5, 3, 1, 0}; // 객체 배열

 

 

---

https://school.programmers.co.kr/learn/courses/30/lessons/42747?itm_content=course14743

프로그래머스