[알고리즘] 프로그래머스 H-index (레벨 2) / 자바 java 풀이

프로그래머스 정렬 문제 중 H-index 문제이다.

 

H-index 문제는 레벨 2 문제로 문제를 푸는데 뭔가 자꾸 헷갈리고 뒤죽박죽 머리 회전이 잘 안되는 느낌이 들었던 문제..🥲

 

📑 H - index

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

문제 설명

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입니다.

 

✏️ 문제 해결 방법

h-index 는 논문 중 최소한 h 번 인용된 논문이 h편 이상이고 나머지 논문이 h 번 이하로 인용된다는 것을 의미한다.

 

1. 논문 정렬

논문을 우선 오름차순으로 정렬해서 비교하게 되면 쉽게 특정 값 이상인 논문의 개수를 비교할 수 있다.

Arrays.sort(citations);

 

2. 인용 횟수와 논문 수 비교

현재 위치에서의 인용 횟수와 그 이후의 인용 횟수를 비교하여 조건을 만족하는지 확인한다. 구해야 하는 값은 현재 논문들 중 최댓값이기 때문에 최대값을 리턴해준다. 

int max = 0;
for(int i = citations.length - 1 ; i>=0 ; i--) {
	int min = Math.min(citations[i], citations.length - i);
    	if(max < min) {
    		max = min;
    	}
}

현재 논문의 인용 횟수와 현재 논문 이후에 있는 논문 개수 중 작은 값을 선택한다. 

➡️ 최소한 h 번 인용된 논문이 h편 이상이고 나머지 논문이 h 번 이하 이기 때문에

예시에 나온 걸 그대로 대입해서 살펴보면 다음과 같다.

1) 정렬후 citations = [0, 1, 3, 5, 6]

2) 
i = 4 / citations[4] = 6 / min = Math.min(6, 1) = 1 / max = 1

i = 3 / citations[3] = 5 / min = Math.min(5, 2) = 2 / max = 2

i = 2 / citations[2] = 3 / min = Math.min(3, 3) = 3 / max = 3

i = 1 / citations[1] = 2 / min = Math.min(1, 4) = 1 / max = 3

i = 0 / citations[0] = 0 / min = Math.min(0,5) = 0 / max = 3

 

위의 코드를 모두 합치면 다음과 같다.

 

 

전체 코드

import java.util.*;

class Solution {
    public int solution(int[] citations) {
        
        Arrays.sort(citations);

        int max = 0;
        for(int i = citations.length-1; i >= 0; i--){
            int min = Math.min(citations[i], citations.length - i);
            if(max < min) max = min;
        }

        return max;
    }
}

 

🕸️ 문제 풀이 소감

간단하게 풀 수 있을거라 생각했는데 생각보다 너무 간단하지 않아서 당황했던 문제이다. 문제 자체가 어렵다기보다 너무 헷갈려서 복잡했다. 뭐가 어떻게 되는거지..? 머리로만 생각하면 절대 안 풀리는 문제였던 것 같다... 😵‍💫

---

궁금한 점이 있거나 잘못된 부분이 있다면 얼마든지 댓글로 남겨주세요 🤗

감사합니다!

 

"이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다."