H-Index

분석

1. 주어진 배열을 내림차순 정렬
2. 현재 인덱스 +1이 현재 인덱스의 원소값 이상인지 판단
   참 - 현재 인덱스의 원소값의 제곱 리턴
   거짓 - 다음 인덱스로 넘어가서 2.를 반복

오류를 고쳐보자

내가 조건을 잘못이해했다. 가장 많은 인용수의 논문을 찾는게 아니라, 현재 논문의 인용수가 i+1 이상인지 확인하는 것이다. 논문의 인용수 조건을 좀 바꿔보자

if (i + 1 > citations[i]) { : 인덱스는 i지만 조건으로 따지는건 i+1이다. 그래서 아예 조건을 반대로 바꾸고 참(=원래 조건에서 거짓)이 되면 이전의 i+1 = i를 내보내게 했다.

모든 조건에서 참(=거짓)이 뜬다면 기본 값으로 length가 뜨도록 했다(원래는 기본값이 0이었기 때문에)

속도를 비교해보자

function sol00(citations) {
  const length = citations.length;
  citations.sort((a, b) => b - a);

  for (let i = 0; i < length; i++) {
    console.log(i + 1, citations[i]);
    if (i + 1 > citations[i]) {
      return i;
    }
  }

  return length;
}

function sol10(citations) {
  let i = 0;

  while (i + 1 <= citations.sort((a, b) => b - a)[i]) i++;

  return i;
}

내 코드는 정렬1회, 반복문1회이므로 $O n(log_{2}N)$의 시간복잡도를 가진다

반대로 다른 사람의 코드는 반복마다 정렬을 하므로 $O(N^2log_{2}N)$의 시간복잡도를 가진다

이 코드를 참조해서 내 코드를 고쳐보자

function sol01(citations) {
  citations.sort((a, b) => b - a);
  let i = 0;

  while (i + 1 <= citations[i] && i < citations.length) {
    i++;
  }

  return i;
}

시간복잡도는 똑같다

속도비교 1

sol10이 상상이상으로 느리다 빼놓고 한번 더하자

속도비교 2

---

$lon_{2}2$ = 1이어서 그냥 2배로만 증가한것같다

원소의 크기는 영향이 없다고 보이고, 배열의 길이에만 영향을 받는다

배운 점

1. 잘 이해가 안될때는 조건을 아예 반대로 하는 것도 좋아보인다
2. 코드를 짧게 짜는데 신경쓰다가 시간복잡도를 엄청나게 늘리지 않게하자