CodingTest/Javascript

[JavaScript] 프로그래머스 정렬 문제 : H-Index

난소히 2024. 5. 10. 17:14

문제 요구사항

H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다.

어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과에 따르면, H-Index는 다음과 같이 구합니다.

어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다.

어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요.

 

​제한사항

  • 과학자가 발표한 논문의 수는 1편 이상 1,000편 이하입니다.
  • 논문별 인용 횟수는 0회 이상 10,000회 이하입니다.

​

입출력 예

citations
return
[3, 0, 6, 1, 5]
3

 

입출력 예 설명

이 과학자가 발표한 논문의 수는 5편이고, 그중 3편의 논문은 3회 이상 인용되었습니다. 그리고 나머지 2편의 논문은 3회 이하 인용되었기 때문에 이 과학자의 H-Index는 3입니다.

​

------------------------------------------------------------

​

일단 이 문제의 큰 문제점은 이해하기가 어렵다는 것이다.

프로그래머스의 질의응답 게시판을 봐도 문제 이해가 안된다는 글이 대부분이다.

그래서 문제를 이해한 바탕으로 다시 설명해보자면,

​

"나머지 논문이 h번 이하 인용되었다면" 이 문구를 무시한다.

어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이면 h의 최댓값이 이 과학자의 H-Index입니다.

즉, 논문이 인용된 횟수가 a번이라고 하면, a번보다 많이 인용된 논문의 개수가 a보다 크거나 같으면 된다.

여기서 중요한 점은, 입력값에 존재하지 않는 인용 횟수도 h값이 될 수 있다는 것이다.

​

위의 입출력 예시로 다시 설명해보면

  • 0 -> 0번 이상 인용된 논문은 0, 1, 3, 5, 6 총 5개이다. 0 < 5 이므로 0은 H-Index의 후보값이 된다.
  • 1 -> 1번 이상 인용된 논문은 1, 3, 5, 6 총 4개이다. 1 < 4 이므로 1은 H-Index의 후보값이 된다.
  • 2 -> 2번 이상 인용된 논문은 3, 5, 6 총 3개이다. 2 < 3 이므로 2는 H-Index의 후보값이 된다.
  • 3 -> 3번 이상 인용된 논문은 3, 5, 6 총 3개이다. 3 = 3 이므로 3은 H-Index의 후보값이 된다.
  • 4 -> 4번 이상 인용된 논문은 5, 6 총 2개이다. 4 > 2이므로 4는 H-Index의 후보값이 될 수 없다.
  • 5 -> 5번 이상 인용된 논문은 5, 6 총 2개이다. 5 > 2이므로 5는 H-Index의 후보값이 될 수 없다.
  • 6 -> 6번 이상 인용된 논문은 6 총 1개이다. 6 > 1이므로 6은 H-Index의 후보값이 될 수 없다.

그럼 후보값 0, 1, 3 중에 가장 큰 값인 3이 H-Index가 된다.

​

다른 예시를 들어보면, [1, 10, 11] 이라는 세 값이 있을 때

  • 1번 이상 인용된 논문은 1, 10, 11로 3개이다. 1 < 3이므로 1은 H-Index의 후보값이 된다.
  • 2번 이상 인용된 논문은 10, 11로 2개이다. 2 = 2이므로 2은 H-Index의 후보값이 된다.
  • 3번 이상 인용된 논문은 10, 11로 2개이다. 3 > 2이므로 3은 H-Index의 후보값이 될 수 없다.

그럼 우리는 세번의 시도 만으로도 답을 알 수 있다.

2가 H-Index 후보값이지만, 3이 H-Index 후보값이 아니라면, 3보다 큰 수 중에서는 H-Index의 후보값이 될 수 있는 값이 없다.

따라서 답은 2이다.

​

위의 방법으로 문제를 이해하고 문제를 풀어보았다.

​

코드

function solution(citations) {
    citations.sort((a, b) => b - a); // 내림차순 정렬

    let sValue = citations[0]; // H-Index는 최댓값이므로, 논문이 가장 많이 인용된 횟수를 시작 값으로 정한다.

    while(true){               // 최악의 경우, 논문이 인용된 횟수 중 최댓값 x citations 배열 길이만큼 돌아야하므로 while문 사용
        let cnt = 0;
        
        for (let i = 0; i < citations.length; i++) {
            if (citations[i] >= sValue) { // citations 배열을 훑으며 sValue보다 크거나 같은 값을 카운트
                cnt = cnt + 1;
            }
        }
        if(cnt >= sValue){     // sValue보다 크거나 같은 값이 sValue보다 많으면 그 값을 H-Index로 정한다.
            return sValue;
        }
        else{
            sValue--;          // 아니라면 기존 sValue에서 1을 뺀 값을 sValue로 정한다.

            if(sValue < 0){    // sValue가 음수 값이라면 citations 배열의 길이를 return한다.
                return citations.length;
            }
        }
        
    }
}

console.log(solution([3, 0, 6, 1, 5])); // return 3
console.log(solution([1, 10, 11])); // return 2
console.log(solution([0, 0, 0, 0, 0])); // return 0

while true 문을 사용하여, 메모리 복잡도가 걱정되긴하지만 이런 식으로 풀이하였다.

아마 더 간단한 풀이도 있을텐데, 문제 이해를 위하여 이렇게 늘여서 작성하였다.