[프로그래머스_Lv2] H-index ( by using JavaScript )

문제

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

코딩테스트 연습 - H-Index

 

How to Solve ?

 

[1] 완전탐색

H-index란, N편의 논문 중에서 h이상 인용된 논문이 h개 이상 있을 때를 의미한다.

 

위의 설명을 아래와 같이 잘못 이해해서 2중 루프 완전 탐색을 하였다.

 

[ 0, 1, 3, 5, 6 ]

 

0 !==  5 (0번 이상 인용된 논문의 수)

1 != 4 ( 1번 이상 인용된 논문의 수 )

3 === 3 ( 3번 이상 인용된 논문의 수 ) => 정답

function solution(citations) {
  const answer = [];
  let result = 0;
  let count = 0;
  citations.sort((a, b) => a - b);

  for (let i = 0; i < citations.length; i++) {
    let tmpH = citations[i];
    citations.forEach((each) => (each >= tmpH ? count++ : count));

    if (tmpH === count) {
      answer.push(tmpH);
    }

    count = 0;
  }

  result = Math.max(...answer);
  return result;
}

 

[2] 

 

내가 잘못 이해한 부분은, H번 인용된 논문의 개수가 H개 여야 한다는 착각을 하였던 것인데 

 

실제로는 H번 이상 인용된 논문의 개수가 H개 이상 있는 경우 중 최대 값을 구하는 것임을 명심하고 문제를 풀어야한다.

 

이해가 다소 어려워, 다음의 예시를 통해 설명을 해보겠다.

 

[  100, 99, 98, 1 ] 인 경우 H-INDEX는 몇일까?  정답을 먼저 말하면 답은 "3"이다.

 

왜 3인지 이해가 안간다면, 아마도 문제를 잘 못 이해 한 것일텐데 citations 안에 있는 값들은 각 논문이 인용된 횟수이고

우리가 구해야 하는 값은 H번 이상 인용된 논문이 H개 이상인 값을 구해야한다.

 

즉,  이를 위해 

 

1) 내림차순으로 정렬하여 큰 값을 앞으로 보내야한다.

 

왜 내림차순으로 정렬을 해야할까?

답은 간단하게 생각하면 쉬운데, H번 인용된 논문의 수를 찾기 위해서는 H라는 값인 1부터 확인을 해야한다.

이 때, H번보다 작은 값이 나온다면 H번 인용보다 적게 인용된 논문이기에 루프를 중단 시켜야 한다. 고로, 내림차순으로 정렬하는 것이 문제의 답을 찾는 첫 번째 열쇠가 된다.

 

2) 루프마다 "H" ( 인용 횟수 ) 를 늘리며 탐색한다.

 

그렇다면 왜 루프마다 H를 늘리며 탐색을 할까? 

 

이에 답하기 위해서는 " n편 중, h번 이상 인용된 논문이 h편 이상이고 " 라는 조건을 올바르게 이해하여야 하는데

예를 들어보자면, 15가 H-index가 되려면 15번 이상 인용된  논문이 15개는 있어야 한다.

 

그렇기 때문에 주어진 값 중에 [ 100, 99, 98, 1] 의 정답이 3이 되는 이유도 98이 되기 위해서는 98번 이상 인용된 논문이 98개가 있어야 하는데 우리에게 주어진 논문의 최대 수는 4이기 때문에 H-INDEX는 4를 넘을 수 없다.

 

고로 내림차순으로 정렬하여 H를 1부터 탐색을 했을 때,

 

만약 H보다 값이 작은 경우가 없다면, 최대 값인 citations의 길이가 출력 되고,

만약 H보다 값이 작은 경우가 있다면, 그 이전의 값이 출력 될 것이다.

 

 

2-1 ) 1차 루프 ( 1회 인용된 논문을 H-index로 가정 => 1회 인용된 논문이 1개 이상 있어야 한다.  )

 

[ 1 < 100 ]

 

만약 "첫번째 값이 1보다 작으면, 가장 큰 값이 1보다 작은 것이기에 H-index는 0이 될 것이고

 

첫 번째 값이 1보다 크다는 것은 1회 이상 인용된 논문이 1개 이상은 있다는 뜻이기에 다음 루프로 넘어가면 된다

 

 

2-2 ) 2차 루프 ( 2회 인용된 논문을 H-index로 가정 => 2회 인용된 논문이 2개 이상 있어야 한다.  )

 

[ 2 < 99 ]

 

[ 2 < 100 ] 

 

두번째 값은 첫 번째 값보다 작다. 고로, 두번째 값이 2보다 크다면 첫 번째 값도 2보다 크다는 것이기에

 

2회 인용된 논문이 2개 이상임을 알 수 있다.

 

 

 

2-3 ) 3차 루프 ( 3회 인용된 논문을 H-index로 가정 => 3회 인용된 논문이 3개 이상 있어야 한다.  )

 

[ 3 < 98 ]

[ 3 < 99 ]

[ 3 < 100 ]

 

세번째 값은 두 번째 값보다 작다. 고로, 세번째 값이 3보다 크다면 첫,두 번째 값도 3보다 크다는 것이기에

 

3회 인용된 논문이 3개 이상임을 알 수 있다.

 

 

2-4 ) 4차 루프 ( 4회 인용된 논문을 H-index로 가정 => 4회 인용된 논문이 4개 이상 있어야 한다.  )

 

[ 4 > 1 ]

[ 3 < 98 ]

[ 3 < 99 ]

[ 3 < 100 ]

 

네번째 값이 각 논문이 인용된 횟수인 H보다 작다는건 , 4이상은 H-index가 될 수 없음을 의미한다.

 

 

function solution(citations) {
  citations = citations.sort((a, b) => b - a);

  let i = 0;
  while (i + 1 <= citations[i]) {
    i++;
  }

  return i;
}