[Algo Rhythm🕺💃] 프로그래머스 고득점 Kit 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회 이하입니다.

 

나는 어떻게 풀었나

 

import java.util.ArrayList;
import java.util.Collections;

public class H {
    int h;
    int upper = 0; // h번 이상 인용된 논문의 수
    int lower = 0; // h번 이하 인용된 논문의 수
    
    public H(int h) {
        this.h = h;
    }
}

class Solution {
    public int solution(int[] citations) {
        int answer = 0;
        int n = citations.length;
        ArrayList<H> candidates = new ArrayList<H>();
        ArrayList<Integer> qualified = new ArrayList<Integer>();
        
        // initialized
        for(int i = 0; i <= n; i++) {
            candidates.add(new H(i));
        }
        
        // pre-processing
        for(H cand : candidates) {
            for(int citation : citations) {
                if(cand.h >= citation) cand.upper++;
                if(cand.h <= citation) cand.lower++;
            }
        }
        
        // check conditions
        for(H cand : candidates) {
            if(cand.h >= cand.upper && cand.h <= cand.lower) {
                qualified.add(Integer.valueOf(cand.h));
            }
        }
        
        answer = (qualified.isEmpty()) ? 0 : Collections.max(qualified);
            
        return answer;
    }
}

 

나는 왜 저렇게 풀었나

 

문제를 읽어보니 0 이상 n 이하의 정수가 h가 될 수 있음을 알 수 있었다. 더 정확한 이해를 위해 [3, 0, 6, 1, 5]이 input으로 주어진 경우를 아래와 같은 표로 정리했다.

 

 

표로 정리하고나니 H가 될 수 있는 조건 두 가지를 통과해야 H-Index가 될 수 있는 자격이 주어진다는 것을 알게 되었다.

 

1) H번 이상 인용된 논문이 H편 이상이어야 한다.

2) 나머지 논문이 H번 이하 인용되어야 한다.

 

그래서 아래와 같은 알고리즘을 생각했다.

 

1) h, h번 이상 인용된 논문의 수, h번 이하 인용된 논문의 수를 멤버로 갖는 H라는 클래스를 만든다.

2) 각 H 후보들의 h번 이하 인용 논문 수, h번 이상 논문 수를 파악한다.

3) H번 이상 인용된 논문이 H편 이상이고 나머지 논문이 H번 이하인 H들을 찾는다.

4) 자격있는 H들 중 최대값을 return한다.

 

import java.util.ArrayList;
import java.util.Collections;

public class H {
    int h;
    int upper = 0; // h번 이상 인용된 논문의 수
    int lower = 0; // h번 이하 인용된 논문의 수
    
    public H(int h) {
        this.h = h;
    }
}

class Solution {
    public int solution(int[] citations) {
        int answer = 0;
        int n = citations.length;
        ArrayList<H> candidates = new ArrayList<H>();
        ArrayList<Integer> qualified = new ArrayList<Integer>();
        
        // initialized
        for(int i = 0; i <= n; i++) {
            candidates.add(new H(i));
        }
        
        // pre-processing
        for(H cand : candidates) {
            for(int citation : citations) {
                if(cand.h >= citation) cand.upper++;
                if(cand.h <= citation) cand.lower++;
            }
        }
        
        // check conditions
        for(H cand : candidates) {
            if(cand.h >= cand.upper && cand.h <= cand.lower) {
                qualified.add(Integer.valueOf(cand.h));
            }
        }
        
        answer = Collections.max(qualified);
            
        return answer;
    }
}

 

처음에는 이렇게 코드를 작성했는데 테스트케이스 16번에서 에러가 생겼다. 다른 사람들 질문을 확인하니까 모두 0일 경우를 처리해야 한다고 그래서 마지막에 qualified 배열이 비어 있을 경우 0을 return 하는 코드를 추가했다.

 

나는 무엇을 배웠나

 

아래 블로그를 통해 자바에서 최대, 최소값을 찾는 여러 방법을 배웠다.

https://www.daleseo.com/java-min-max/

 

처음에는 Stream을 사용해서 간결하게 표현하려고 했지만 에러가 떠서 다른 방법을 사용해야 했다.

Java8을 더 공부해서 이 부분을 보충해야겠다고 생각했다.