리트코드 - 274. H-Index

리트코드 - 274. H-Index

출처 - https://leetcode.com/problems/h-index/description/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

주어진 정수 배열 citations에서 citations[i]는 연구자가 i번째 논문에 받은 인용 횟수입니다. 연구자의 h-index를 반환합니다.

위키피디아의 h-index 정의에 따르면, h-index는 주어진 연구자가 적어도 h번 이상 인용된 논문이 h편 이상이 되도록 하는 최대 값으로 정의됩니다.

 

의사코드

citations 배열 정렬 int n = citations.length 반복문 시작(i = 0, i < n까지)     if (citations[i] >= n - i)         n - i 리턴 반복문종료 0 리턴

 

풀이코드

class Solution {
    public int hIndex(int[] citations) {
        Arrays.sort(citations);
        
        int n = citations.length;

        for (int i = 0; i < n; i++) {
            if (citations[i] >= n - i) {
                return n - i;
            }
        }

        return 0;
    }
}

코드설명

배열에서 n 이상인 수가 n개 이상인지를 판별하는 문제이다.

갯수를 구하는 것이기 때문에 정렬을 이용하여 풀면 된다.

 

먼저 배열을 오름차순으로 정렬하여 첫번째 배열값부터 확인하면 된다.

예를 들어 배열이 {3,4,5} 라면, 첫번째 배열만 크기인 3보다 큰지 확인하면 된다.

오름차순이기 때문에 이값이 3보다 크다면 나머지 값은 모두 3 이상이기 때문이다.

 

만약 3보다 작다면 다음값을 확인하여 이 값이 하나 작은 2보다 큰지 확인하면 된다.

이를 반복문으로 표현하면 아래와 같다.

int n = citations.length;
int answer = n;

for (int i = 0; i < n; i++) {
    if (citations[i] >= answer) {
        return answer;
    }
    answer--;
}

여기서 n을 직접 줄이면 안되는 이유는 실제로 반복문이 n까지 돌고있기 때문에 n을 줄이면 배열 전체를 순회하지 못하게 된다.

따라서 answer라는 변수를 두고 이 값을 줄이면 된다.

 

이런식으로 확인하여 모든 배열을 확인하지 않고, 만족하는 값을 찾으면 바로 값을 리턴할 수 있다.

코드를 잘 보면 i가 증가하는 만큼 answer가 감소하고 있다.

즉, answer를 사용하는 대신 i를 이용하면 풀이코드에서와 같은 식으로 리팩토링이 가능하다.

 

시간복잡도 - O(n log n) (O(n)이 아닌 이유는 Arrays.sort 때문)

공간복잡도 - O(1)

 

문제를 풀며 생각한 흐름과 배운 점

DP를 풀다가 다시 Array를 봐서 그런가 생각하고 구현하는 것은 그렇게 어렵지 않았다.

단 시간이 2ms로 뭔가 애매했는데, 나름 70%으로 상위권임에도 시간을 더 줄여보고 싶었다.

 

그렇지만 기존 방법으로는 시간을 줄이기가 어려워서 다른 코드를 보기로 했다.

 

다른 코드 1

class Solution {
     public int hIndex(int[] citations) {
        Arrays.sort(citations);
        int n = citations.length, res = 0;
        for(int i = 0; i < n - res; i++)
            if(citations[i] != res)
                res = Math.max(res, Math.min(citations[i], n-i));
        return res;
    }
}

이 코드에서는 반복문의 끝이 n - res로 도는 횟수가 유동적으로 줄고 있다.

res는 조건에 따라 값을 갱신하는데, 이 부분이 독특하다.

먼저 citations[i]와 n - i을 비교하여 작은 값을 선택하여, 이 값과 res 값중 큰 값을 선택하여 갱신한다.

 

만약 배열의 첫번째 값이 n - i보다 큰 경우 바로 종료되어 res가 리턴되고, n - i보다 작은 경우 배열 값으로 res가 갱신될 것이다.

내 코드와 같이 배열 값이 n - 1 값보다 작은지 비교하는 로직이지만 구현한 방식이 다른 코드다.

다른 코드 2

class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        int[] freq = new int[n + 1];
        for(int num : citations){
            if(num > n) freq[n]++;
            else{
                freq[num]++;
            }
        }
        int sum = 0;
        for(int i = n; i >= 0; i--){
            sum += freq[i];
            if(sum >= i) return i;
        }
        return 0;
    }
}

이 코드는 런타임이 0ms로 최상급이다.

Arrays.sort를 사용하지 않고, 마치 dp 배열을 사용한 것처럼 freq배열을 사용했다.

값을 분류하여 freq에 넣고, 이 값을 뒤에서부터 더하다가 i보다 크다면 i를 리턴한다.

 

배열을 어떻게 활용하느냐 를 본받을 수 있는 좋은 코드였다.

 

정리

배열에서 n 이상이 n번 있는지 확인하는 방법