프로그래머스[Java] - H-Index(정렬)

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

코딩테스트 연습 - H-Index

코드

import java.util.Arrays;

class Solution {
     public int solution(int[] citations) {
        int answer = 0;
        int size = citations.length;

        Arrays.sort(citations);
        int max = max(citations);

        for (int i = 0; i < max; i++) {
            int higherThanH = 0;

            if (contains(citations, i)) {
                higherThanH = 1;
            }

            for (int j = 0; j < size; j++) {
                if (citations[j] > i) {
                    higherThanH++;
                }
            }
            if (higherThanH >= i) {
                answer = i;
            }
        }

        return answer;
    }

    private static int max(int[] arr) {
        return arr[arr.length - 1];
    }

    private static boolean contains(int[] arr, int element) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == element) {
                return true;
            }
        }
        return false;
    }
}

 

풀이

문제를 이해하는데도 시간이 꽤 걸린것 같다...

 

일단 문제 분류가 정렬이어서, 정렬을 통해 문제를 좀 더 쉽게 풀수 있는 것 같다.

 

어떤 과학자가 발표한 논문 n 편 중, h번 이상 인용된 논문이 h 편 이상이고, 나머지는 h번 이하 인용 => h의 최댓값

 

위 말이 사실 굉장히 헷갈렸다... 문제에서 주어진 배열(citations)을 정렬하면 아래와 같다.

 

위 배열에서 논문의 수(n)는 총 5편이고, 3을 기준으로 하면 (h = 3)

3번 이상 인용된 논문 = 3 , 나머지는 3번 이하 인용(정렬을 통해 이부분은 항상 True) 으로 만족해서 H-Index는 3이다.

 

여기서 주의해야 할점이, H-Index의 후보가 될 수 있는 수는 배열에 있는 수가 전부는 아니다.

 

 

 

만약 위와 같이 citations의 배열의 정렬이 0, 1, 3, 5, 6, 7, 8 일 경우 최댓값은 3이 될거라고 생각을 했지만,

배열에 존재하지 않는 4를 대입해보면 4편 이상 인용된 논문이 4개(5, 6, 7, 8) 이므로

H-Index는 4가 된다.

 

따라서 h번 이상 인용된 논문을 판단할 때는, 배열의 최솟값 ~ 배열의 최댓값 까지의 수를 기준으로 H-Index를 구해야 한다.

문제에서 주어진 논문별 인용 횟수는 Max가 10,000회 이므로 완전탐색을 하더라도 시간초과가 발생하지 않는다.

 

 

코드 풀이

 - 먼저 배열의 정렬과, 배열에서 최댓값을 찾는다.

        Arrays.sort(citations);
        int max = max(citations);
        
        private static int max(int[] arr) {
            return arr[arr.length - 1];
        }

 

 - 그 후 코드에서 h 번 이상 인용된 논문에서 h의 값을 for문의 변수인 i로 사용한다.

 

위 그림과 같이, 현재 비교하고자 하는 h의 값이 배열에 존재하지 않는 경우는 h 번 이상 인용된 논문이라고 할 수 없으므로 초기값을 0으로, 배열에 존재할경우 초기값을 1로 설정한다.

            int higherThanH = 0;

            if (contains(citations, i)) {
                higherThanH = 1;
            }

 

 - 다음으로 내부 for문에서 비교할 h의 값보다 배열의 값이 클 경우(h번 이상 인용된 논문) higherThanH +1을 해준다.

            for (int j = 0; j < size; j++) {
                if (citations[j] > i) {
                    higherThanH++;
                }
            }

 

- 최종적으로 h번 이상 인용된 논문이 h 편 이상일 경우 ==> H-Index의 값을 비교한 h(for문의 i변수) 값으로 갱신한다.

            if (higherThanH >= i) {
                answer = i;
            }

 

 

 

 

 

다른 코드

import java.util.Arrays;

class Solution {
    public int solution(int[] citations) {
        int answer = 0;
        Arrays.sort(citations);
        for(int i=0; i<citations.length; i++){
            int smaller = Math.min(citations[i], citations.length-i);
            answer = Math.max(answer, smaller);
        }
        return answer;
    }
}

허메 ...... 단순하지만 잘 이해가 안된다 ..;;