[Programmers] 42747. H-Index

• 성능 요약
• 구분
• Answer Code1(2023.02.06)
• 문제 풀이
• Review

문제 링크

성능 요약

메모리: 76 MB, 시간: 0.36 ms

구분

코딩테스트 연습 > 정렬

Answer Code1(2023.02.06)

import java.util.*;

class Solution {
    public int solution(int[] citations) {
        int answer = 0;
        int h = 0;
        int max = 0;
        
        //1.
        Arrays.sort(citations);
        
        //2.
        for(int i = 0; i < citations.length; i++) {
        
            //2-1
            int smaller = Math.min(citations[i], citations.length-i);
            
            //2-2
            if(smaller >= answer) {
                answer = Math.max(answer, smaller);
            }
            else {
                break;
            }
        }
        
        //3.
        return answer;
    }
}

문제 풀이

• 전체 논문의 인용횟수를 값으로 가진 배열에서 전체 n편 중 h편의 논문이 h회 이상 인용되었을 때

  h의 최대값인 H-Index을 구하는 문제다.

• 논문 수의 n과 H-Index가 될 수 있는 h의 관계는 h <= n으로 표현할 수 있다.

1. 인용횟수 배열을 정렬한다.

2. 인용횟수 배열 요소 값을 차례로 h로 지정하며 H-Index 조건에 부합하는지 확인한다.

   • h의 최대값을 구하기 때문에 h는 논문의 최대 수인 n부터 -1씩 감소하는 것으로 시작한다(citations.length-i)

   • [2-1]조건: 현재(해당 요소) 논문의 인용횟수(citations[i]) >= h회 이상 인용된 논문 개수(citations.length-i)

   • 현재 논문의 인용횟수와 현재 논문보다 인용횟수가 크거나 같은 논문의 개수 두 값 중 작은 값이 H-Index로 지정되어야

   • “전체 n편 중 h편의 논문이 h회 이상 인용”이라는 말이 무조건 참이 되므로

   • [2-2]두 값 중 최소값을 갖는 임시 H-Index 값을 지정하고, 오름차순으로 정렬된 요소들에 차례대로 접근하여 최대값을 갱신해 나간다.

   • 더 이상 값이 증가하지 않고, 감소되는 구간에서는 반복을 중지한다(최대값을 구하기 때문)

3. 조건에 부합하는 h의 값들 중 최대값인 H-Index를 출력한다.

Review

• 처음에는 제대로 이해가 되질 않아서 바로 그림을 그려나가니까, 이해가 되었다.

• 2번 조건에 부합하는 것을 코드로 옮기는 작업이 오래 걸렸지만, 이해와 또 다른 알고리즘을 알게 되어서 좋았다.

• 문제에 대한 이해와 어떻게 풀어야하는 지 알기 시작한 이후부터는 최대한 메모리와 시간을 최소화하기 위해 효율적으로 구현하려고 노력했다.