알고리즘 Programmers 정렬 Level 2 [H-index] / javascript

H index

Programmers 정렬 Level 2 중 H-index 알고리즘 문제를 풀었습니다.

문제 설명 이미지

입출력 예와 설명을 듣고 해석하면, 논문이 인용된 횟수인 citations 를 순회하면서
h 번 이상 인용된 논문이 h 개보다 같거나 많을 경우를 의미 그 값 중 최대값을 의미한다고 해석했습니다.

function solution(citations) {
    for (let i = citations.length; i >= 0; i--) {
        const citationElement = citations.filter((element) => element >= i).length;
        if (citationElement >= i) {
            return i;
        }
    }
}

기준을 citations 배열의 length 로 두고 싶었기에, 순회 기준을 citations.length 로 두었습니다.
위와 같은 기준을 둔 이유는 아래와 같습니다.
h 번 이상 인용된 논문이 h 개보다 같거나 많을 경우 그 중 최대값이라는 뜻은 논문을 작성하신 개수만큼 인용되었다면
그 값이 최대 값일 것이며, 그렇다면 논문을 작성하신 값에서 1씩 차감하면서 인용된 값을 비교하면
쉽게 해결할 수 있을 것 같다는 생각이였습니다.

1번 순회 시 내부에서 filter 로 논문의 길이와 각 인용된 횟수를 비교하는 방식입니다.
문제의 입출력 예시인 [3, 0, 6, 1, 5] 로 풀이를 작성해보곘습니다.

<첫번째 순회>
citations.length 는 5 이며, 첫 순회 시 i 의 값은 5입니다.
그리고 citations 배열을 filter 로 5 이상의 값의 길이를 확인합니다.
citations 배열에서 5 이상의 값은 [6, 5] 이며, 이는 length 에는 못미치는 값입니다.

<두번째 순회>
두번째 순회 시 i 의 값은 4입니다.
동일하게 filter 로 4 이상의 값의 길이를 확인합니다.
이 때 4 이상의 값은 첫번쨰 순회와 동일하게 [6, 5] 이며, 해당 길이는 2, 4보다 작습니다.

<세번째 순회>
세번째 순회 시 i 의 값은 3입니다.
3 이상의 값을 확인하고, 이는 [3, 5, 6] 입니다. 길이는 3 , i 의 길이도 3 이므로
조건인 이상에 적합합니다.

그러므로 결과는 3 입니다.

뭔가 되게 복잡하고 어렵게 풀었다는 생각이 들어 다른 사람의 풀이를 보았습니다. 

function solution(citations) {
     citations = citations.sort(sorting);
     var i = 0;
     while(i + 1 <= citations[i]){
         i++;
     }
     return i;


     function sorting(a, b){
         return b - a;
     }
}

sorting 을 통해 내림차순으로 정리한 후, 이를 순회하면서 계산하는 방식입니다.
우선 시간 복잡도 기준으로 제가 작성한 로직은 n2 에 해당하며 아래와 같은 속도를 확인할 수 있습니다.

(for 문 내에서 filter 로 다시 순회)

타 풀이의 시간 복잡도는 2n, 여기서 상수는 제거하므로 n 인 방법이네요.

생각보다 문제 풀이 시간이 오래 걸리기도 했고, 앞으로도 많은 연습이 필요할 것 같습니다.

 

소요시간

40분