[프로그래머스]정렬: H-Index (level 2)

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

코딩테스트 연습 - H-Index | 프로그래머스

 

 

안 좋은 답안

import java.util.Arrays;
 
class Solution {
    public int solution(int[] citations) {
        
        // 오름차순 정렬
        Arrays.sort(citations);
 
        int iMaxRefCount = citations[citations.length - 1];
        int answer = 0;
        
        // 최다 인용 횟수만큼 반복문
        for (int i = 0; i <= iMaxRefCount; i++) {
            
            int iAboveCount = 0;
            int iUnderCount = 0;
            
            // 1번째 논문부터 끝까지 체크해서 카운팅
            for (int j = 0; j < citations.length; j++) {
                if (citations[j] >= i) {
                    iAboveCount++;
                }
                if (citations[j] <= i) {
                    iUnderCount++;
                }
            }
            
            // 횟수n <= n회 이상 인용된 논문 개수 && 횟수 n >= n회 이하 인용된 논문 개수
            if (i <= iAboveCount && i >= iUnderCount) {
                answer = i;
            }
        }
        return answer;
    }
}
 

 

 

좋은 답안 A

import java.util.Arrays;
import java.util.Collections;
 
class Solution {
    public int solution(int[] citations) {
        
        // int배열 -> Integer배열
        Integer[] arrCitations = new Integer[citations.length];
        
        for (int i = 0; i < citations.length; i++) {
            arrCitations[i] = citations[i];
        }
        
        // 내림차순 정렬
        Arrays.sort(arrCitations, Collections.reverseOrder());
 
        for (int i = 1; i <= arrCitations.length; i++) {
            
            // 논문 인용된 횟수 < (h + 1)번째 논문  이면 h 리턴  
            if (arrCitations[i - 1] < i) {
                return i - 1;
            }
        }
        return citations.length;
    }
}
 

 

좋은 답안 B

import java.util.Arrays;
 
class Solution {
    public int solution(int[] citations) {
        
        // 오름차순 정렬
        Arrays.sort(citations);
 
        for (int i = 1; i <= citations.length; i++) {    
            
            int iMaxIndex = citations.length - i + 1;
            
            // 논문 인용된 횟수 >= h번째 논문 이면 h리턴
            if (citations[i - 1] >= iMaxIndex) {
                return iMaxIndex;
            }
        }
        return 0;
    }
}

 

답안 B가 A보다 더 빠르다.

하지만 문제를 이해하기에는 답안 A가 더 좋은 것 같다. 

 

 

논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 
나머지 논문이 h번 이하 인용되었다면 h가 이 과학자의 H-Index

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

 

내가 처음에 짠 소스는 정말 무식한 방법이었고,

A B 둘에 비해하면 형편없이 느리다ㅠㅠ

최대 인용 횟수를 기준으로 하니, 10000번을 돌릴 수도 있는 것이다. 

논문 갯수를 기준으로 하면 많아봤자 1000번 돌렸을텐데

 

다른 사람의 풀이를 보니 문제가 그제서야 이해됐다. 

 

 

1. 문제를 간소화해서 표현해도 된다. 

▶h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용

문제에서 이렇게 나와있다고, 나머지 논문에 대해서도 코딩할 필요는 없다.

 

논문이 10편이라 할때, 논문 7편이 h번 이상 인용되었다면 3편은?

☞ h편 "이하" 인용되었겠지 ㅎㅎ 

조건인 척 하는 사족을 잘 구별해야 한다. 

 

 

2. 개수는 index를 말하는 것이다

왜냐면, 정렬했기 때문이다. 

 

[3, 0, 6, 1, 5] 배열을 내림차순 정렬하고 여기에 index를 1부터 매겨보자.

배열  index
6     // 1
5     // 2
3     // 3
0     // 4
1     // 5
 

6번 이상 인용된 논문 갯수는? → 1개

5번 이상 인용된 논문 갯수는? → 2개

3번 이상 인용된 논문 갯수는? → 3개

...

 

즉,

h번 이상 인용된 논문이 h편 이상  ≡  D[ i ] ≥ i 

이라는 뜻이다.

문제는 그러한 h의 최대값을 구하는 것이었다. 

 

 

내림차순 정렬한 답안과 오름차순 정렬한 답안의 구현 디테일이 조금씩 달라질 수 밖에 없다. 

자세한 것은 주석 참고 ,,,