🔥[99클럽 코테 스터디] 12일차 TIL - 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입니다.

---

✏️풀이

첫 번재 시도

우선, 문제의 규칙을 찾을 때, 입력 배열을 오름차순으로 정렬하면 더 쉽게 찾을 수 있을 거 같아 Arrays.sort()함수로 정렬을 해 주었다.

그리고 citations배열을 순회하며, 해당 원소 값보다 큰 원소의 갯수가 크고, 남은 원소의 갯수가 원소보다 작으면, 해당 원소 값을 그대로 반환해주도록 구현을 하였다.

import java.util.*;

class Solution {
    public int solution(int[] citations) {
        int answer = 0;
        Arrays.sort(citations);
        
        if (citations.length == 1) {
            answer = 0;
        }
        
        else {
            for (int i = 0; i < citations.length; i++) {
                if (citations.length - i >= citations[i] && i + 1 <= citations[i]) {
                    answer = citations[i];
                }
            }
        }
        return answer;
    }
}

그러나 결과는 실패였다. 그 이유는 문제 이해를 잘 못했기 때문이다🫨

h가 입력 배열 안에 있는 요소 중 하나일 것이라 생각하고 접근을 했었는데, 문제를 다시 천천히 이해해 보니 h는 citations의 요소와는 별개로, 그저 정수 값의 최대값이었다.

두 번째 시도

두 번째 시도에서는 규칙을 몇 가지 찾을 수 있었다.

import java.util.*;

class Solution {
    public int solution(int[] citations) {
        int h = 0;
        Arrays.sort(citations); // 오름차순 정렬
        
        // 길이가 1인 경우
        if (citations.length == 1) {
            if (citations[0] == 0) {
                h = 0; // [0]인 경우
            }
            else {
                h = 1; // [1]인 경우
            }
        }
        else if (citations[0] >= citations.length) {
            h = citations.length;
            // 입력 배열의 첫 번째 요소가 길이랑 같은 경우
            // 길이가 H-Index이다.
        }
        else {
            int temp = citations[0];
              
            while(true) {
                int count = 0; 
                for (int i = 0; i < citations.length; i++) {
                    if (citations[i] >= temp) {
                        count++;// temp보다 큰 요소의 갯수 저장
                    }
                }
                    
                if (count > temp) {
                    temp++; // 갯수가 temp보다 크면 temp 1 증가 후 while문 반복
                }
                else {          
                    if (count < temp) {
                        h = temp - 1; // 갯수가 temp보다 작으면 temp 1 감소
                    }
                    else {
                        h = temp; // 갯수가 temp랑 같다면 H-Index에 temp 저장
                    }
                    break;
                }  
            }
        }
        return h;
    }
}

여러 케이스를 고려해 보니, 예외 처리를 먼저 해주어야 겠다는 생각이 들었다.

내가 발견한 세 가지 예외는 아래와 같다. 단, 여기서 언급된 citations배열은 오름차순으로 정렬된 citations이다.

• citations의 길이가 1이고 첫 번째 원소가 0인 경우
• citations의 길이가 1이고 첫 번째 원소가 1인 경우
• citations의 첫 번째 원소가 citations의 길이랑 같은 경우

이 세 가지 케이스는 출력 값이 일정하기 때문에, 조건문으로 각각 분기해 문제에서 요구하는 답을 출력하도록 구현했다.

이제, 일반적인 케이스를 구현해야 한다.
temp를 하나 만들어 citations의 첫 번째 원소를 저장해 주었고, citations를 쭉 순회하면서, temp보다 큰 값의 갯수를 count해 주었다.

만약, count가 temp보다 크면, 최댓값을 더 찾아갈 수 있다는 의미이기 때문에 temp에 1을 더해 반복문을 더 돌 수 있도록 하였다.

그리고 만약, count가 temp보다 작다면, 해당 temp값은 최댓값보다 1이 더 크다는 의미이기 때문에, temp에 1을 뺀 값을 최종 H-Index에 저장해 주었다. 그런데, count가 temp랑 같은 경우라면, temp가 바로 최댓값이라는 의미이기 때문에, temp를 바로 H-Index에 저장해줌으로써, 모든 경우의 수를 다 고려할 수 있었다.

---

다른 풀이

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 paper = len - i;
            if (citations[i] >= paper) {answer = paper; break;}
        }

        return answer;
    }
}

문제를 풀고, 다른 분들의 풀이를 보니,, 훨씬 더 간결하게 구현할 수 있는 규칙성이 있었다..

오름차순으로 정렬된 배열에서 한 요소보다 큰 요소의 개수를 찾으려면, 그냥 배열의 길이에다가 인덱스 값을 빼주면 되는 것이었다.

그렇게 되면, 배열의 길이가 1인 경우를 따로 고려하지 않아도 되고, while문을 돌 필요도 없어서 시간적으로도 훨씬 효율적이다.

이처럼 문제와 조건을 그대로 받아들이기 보다는, 흐름을 파악하고 필요한 규칙들만 선별해내는 과정이 중요하다는 걸 뼈저리게 느낄 수 있었던 문제였다😂

---

🔗문제 링크
💻Repository