[TIL] 2일차 - Jacoste 알고리즘

2일차 알고리즘 스터디!
문제가 꽤나 어려웠다. 생각보다 안풀려고 고생을 많이했다.
카카오 문제는 어렵다는 생각에 두려움부터 갖고 시작해서 그런가 더 어려운거 같기도 하고...?

오늘은 스터디하면서 많이 혼났다.
C언어처럼 알고리즘 풀려고 스터디하는게 아닌데 자꾸 C언어로 문제를 풀고 말아버린다.

c언어로 풀 수 있기는 하지만, 이를 다시 메서드로 바꾸고 자바스크립트 코드처럼 리팩토링 해야하는데 그 과정을 하지 않아서 문제가 있어보인다. 시간 내서 공부를 다시 해야할 필요가 있다.

프린터, 뉴스클러스터링, K진수에서 소수 개수 구하기 세 문제 풀었다.

🎰 K진수에서 소수 개수 구하기

소수 개수 구하기 문제가 가장 의아했다. 시간 복잡도를 많이 생각해보려고 했는데 결과적으로 내 코드가 가장 느리게 풀렸다. 왜일까?

function solution(n, k) {
  let knum = n.toString(k).split('0');
  let tmp;
  let cnt = 0;

  for (let i = 0; i < knum.length; i++) {
    if (+knum[i] === 2) {
      cnt++;
      continue;
    }
    if (+knum[i] % 2 === 0 || +knum[i] === 1 || knum[i] === '') continue;
    tmp = 3;
    while (tmp <= Math.sqrt(+knum[i])) {
      if (+knum[i] % tmp === 0) break;
      tmp += 2;
    }
    if (tmp > Math.sqrt(+knum[i])) cnt++;
  }
  return cnt;
}

이중 루프가 당연히 필요하다고만 생각하고 풀었었는데, 다른 스터디원들의 코드를 보니 아니었다. 혼자만 복잡하게 생각하고 문제를 풀었었다. 아래는 동료의 코드이다.

function solution(n, k) {
    const checkPrime = (num) => {
        if (num === 2 || num === 3) return true
        for (let i = 2; i <= Math.sqrt(num); i++) {
            if (num % i === 0) return false;
        }
        return true
    }
    return n.toString(k)
            .split('0')
            .filter((x) => x !== '1' && x !== '' && checkPrime(+x))
            .length;
}

동료의 코드에서 보면 시간복잡도 O(n)을 가지는 filter메소드 조건 내부에 for문이 존재하기 때문에 결국 내 코드와 같이 이중 루프문을 가진다고 생각을 했는데, 제일 느렸다.

그래서!! 그래서!! 내 코드를 하나씩 다 뜯어봤다. 줄어든 결과!!

왼쪽 위 결과는 초기 코드의 결과 값이다. 동료의 결과값은 12.96ms가 나왔는데 난 10배 이상 느렸다. 다양한 고민을 해보고 처음에 줄인 것은 while문의 조건에서 Math.sqrt함수 사용을 줄여보는 것이었다.
for문에 들어오자마자 변수를 하나 만들어주고 Math.sqrt값을 변수에 저장시켜놓고 while문의 조건에 변수를 넣는 방법을 사용했더니 130대에서 70대까지 줄어들었다.
그 뒤로 고민을 한참 하다보니 값을 저장해주는 부분의 위치를 내리면 될 것 같았다. 그래서 for문 시작 부분에서 while문 위로 옮겼더니 40대까지 줄어들었다!

이후에 정말 다양한 고민을 했지만 아무리 생각해도 로직상 시간이 더 줄어들 부분이 없었다. 동료의 코드에서 보아도 로직상 문제가 없는데, 심지어 while문도 나는 홀수만 확인해서 더 빨라야하는데 동료코드보다 4배는 더 드렸으니 말이다.
그러다가 갑자기 문득 눈에 띈게 +knum[i]였다. +를 통해 number로 암묵적 타입 변환을 시켜주는데, 타입 변환이 계속해서 일어나다보니 느려진 것이었다. 이 부분까지 고쳐주고 나나 5.77ms라는 약 25배 이상 빨라진 경이로운 결과를 만들어낼 수 있었다!!

최종 코드는 다음과 같다.

function solution(n, k) {
    let knum = n.toString(k).split('0');
    let num = 0;
    let tmp;
    let cnt = 0;
    let sqrt = 0;
    
    for(let i = 0; i < knum.length; i++)
    {
        num = +knum[i];
        if (num === 2)
        {
            cnt++;
            continue;
        }
        if (num % 2 === 0 || num === 1 || num === '')
            continue;
        sqrt = Math.sqrt(num);
        for (tmp = 3;tmp <= sqrt; tmp += 2)
            if (num % tmp === 0)
                break;
        if (tmp > sqrt)
            cnt++;
    }
    return cnt;
}

물론 여전히 c의 모습은 벗어나지 못했다.
메서드를 사용해서 줄이는 연습은 차차 진행할 예정이다. 물론... 여유롭게 진행은 안되지만 추후에..!!

지난주 스터디 결과였는데 시간 복잡도 관련해서 계속 마음에 걸렸던 문제였다. 다행이 원인을 찾고 타입 변환과 시간복잡도 등 이미 알고 있던 부분도 제대로 인지하지 못하고 있음을 깨닫게 되었고, 이번 경험으로 큰 성장을 하게 되었다! 타입 변환 앞으로도 지켜보겠어...!!