[프로그래머스] Lv.2 H-index

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

프로그래머스

 

문제 접근 방법

1. 배열을 정렬해준다.

2. h의 최댓값을 구해야 하므로 뒤에서 부터 순회를 하며 배열값이 h보다 커질 때를 찾는다.

import java.util.*;
class Solution {
    public int solution(int[] citations) {
        Arrays.sort(citations);
        for(int h = citations.length; h >= 1; h--) {
            if (isValid(citations, h)) return h;
        } 
        return 0;
    }
    
    public boolean isValid(int [] citations, int h) {
        int idx = citations.length - h;
        return citations[idx] >= h;
    }
}

 

문제 풀이 회고

 

만약에 정렬을 하지 않고 O(N^2) 시간 복잡도로 문제를 해결하려고 한다면, 10,000 * 10,000이 1억이 되어서 시간초과가 발생할 것이다. 그렇기 때문에 정렬을 하는 시간복잡도 , O(NlogN)을 사용한다면 13만으로 총분히 시간내에 통과가 가능하다.

 

[3, 0, 6, 1, 5]

문제에서 주어진 예제를 정렬하면

[0, 1, 3, 5, 6]

이 된다. 

 

문제에선 h번 이상 인용된 논문에서 h값의 최댓값을 찾아야 한다.

0은 5번 이상 인용,

1은 4번 이상 인용,

3은 3번 이상 인용,

5와 6부터는 2, 1번이상 인용이기 때문에 성립하지 않는다.

 

그렇기 때문에 0,1,3중에서 최댓값인 3이 답이 된다.