Level 2️⃣ - H-Index

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

프로그래머스

---

🚀문제 해석

문제를 잘 읽자!

당연한 말이면서도 문제를 제대로 읽지 않아 여러 시도를 실패했다.

문제에서 정의한 H-Index는 논문 n편 중, h번 이상 인용된 논문의 갯수가 h편 이상이고, 그 외 나머지 논문들이 인용된 갯수는 h번 이하일 때, h의 최댓값을 의미한다.

 

function solution(citations) {
    let ret = Number.MIN_SAFE_INTEGER;
    let max = Math.max(...citations);
    for(let h = 0; h <= max; h++){
        let a = 0;
        let b = 0;
        for(let i = 0; i<citations.length; i++){
            if(citations[i] >= h) a++;
        }
        if(a < h) continue;
        for(let j = 0; j<citations.length; j++){
            if(citations[j] < h) b++;
        }
        if(b > h) continue;
        ret = Math.max(ret, h);
    }
    return ret;
}

코드를 분석하면서 왜 이 코드를 적었는지 이유를 스스로 설명해보자.

 

let max = Math.max(...citations);

먼저 인용된 횟수의 max 값을 구한 이유는 max값보다 큰 횟수로 인용된 데이터는 없기 때문이다.

만약 max가 6이면 6보다 큰 7번만큼 인용된 논문의 갯수가 7이상일 순 없다. 당연한 말이다. 그렇기에 최댓값을 구해주었다.

 

    for(let h = 0; h <= max; h++){
        let a = 0;
        let b = 0;
        for(let i = 0; i<citations.length; i++){
            if(citations[i] >= h) a++;
        }
        if(a < h) continue;
        for(let j = 0; j<citations.length; j++){
            if(citations[j] < h) b++;
        }
        if(b > h) continue;
        ret = Math.max(ret, h);
    }

핵심 로직이다. h의 범위는 0부터 max값까지이다.

만약 h번 이상 인용된 논문이 있다면 a를 더해주면서 갯수를 세어준다.

그리고 a의 갯수가 h번 보다 작다면 문제에서 정의한 H-Index 조건에 맞지 않기 때문에 넘어간다.

만약 a의 갯수가 h번 이상이라면 즉, h번 이상 인용된 논문의 갯수가 h번 이상이라면 나머지 논문의 갯수가 h번 이하인지 판단해야한다. 그래서 앞전에 인용된 횟수가 h번 이상인 논문의 갯수를 세었으니 이번에는 나머지에 해당하는 인용된 횟수가 h번보다 작은 논문의 갯수를 세어준다. 그리고 만약 h번보다 작은 논문의 갯수가 h번을 넘었다면 이 또한 조건에 맞지 않으므로 넘어간다. 그리고 조건에 부합하는 h들 중 최댓값을 찾아주면 된다.

 

🤔코너 케이스 생각하기

문제를 제대로 이해하지 않고 시도해 틀린 이유도 있지만 이 문제는 테스트 케이스가 하나 뿐이었고, 다양한 코너 케이스를 생각하지 않아 틀린 경우도 있었다.

예를 들어 배열이 주어진다면 배열 길이의 최대/최소, 원소의 최대/최소가 코너 케이스가 될 수 있고, 모든 원소가 같은/다른, 오름차순/내림차순 배열도 코너 케이스입니다.

 

처음에는 h의 범위가 0부터 max가 아니라 min 즉, 인용횟수의 최솟값부터 max까지로 생각했었다.

문제에서 주어진 테스트 케이스는 통과했지만 제출할 때마다 번번히 실패를 했기에 반례를 찾기 위해 코너 케이스를 생각했다.

 

만약 인용 횟수의 최솟값인 [0] 이 데이터로 주어진다고 생각해보자.

그렇다면 min값은 0이되고 max값도 0이된다. 이 경우에 조건을 만족하는 H-Index는 0이다. 

 

그렇다면 인용 횟수의 최댓값인 [10_000]이 데이터로 주어진다고 생각해보자.

마찬가지로 min값은 10_000, max값도 10_000이다.

그런데 이때 H-Index는 1이다. 하지만 h는 min과 max가 같기 때문에 10_000만 될 수 있으므로 정확한 값이 나오지 않는다.

 

이렇게 코너 케이스를 생각하면서 내가 구현한 코드가 올바른지 체크해야한다. 항상 반례를 염두해두자. 주어진 테스트케이스에 의존하지 말자.

 

다른 풀이

H-Index의 정의를 제대로 이해하고 정렬을 활용한 코드이다.

function solution(citations) {
    citations.sort((a,b)=>b-a);
    let i = 0;
    while(i+1 <= citations[i]) i++;
    return i;
}