[JavaScript/프로그래머스] 연습문제 - 기사단원의 무기

문제 링크

프로그래머스

 

---

 

초기 정답 코드 - 소인수분해 로직 사용

기존 우리가 알고 있던 약수를 구하는 가장 기본적인 for 문 로직으로는 시간 초과가 발생하였습니다.

그래서 소인수분해를 통해 얻은 각 인수들의 지수+1 을 더하는 로직을 사용하여 문제를 해결했습니다.

function solution(number, limit, power) {
  let answer = 1;

  // 소인수 분해 함수 정의
  function primeFactorization(num) {
    const factors = {};
    let divisor = 2;

    // num이 1보다 클 때까지 반복하며 소인수를 구함
    while (num >= 2) {
      if (num % divisor === 0) {
        factors[divisor] = (factors[divisor] || 0) + 1;
        num /= divisor;
      } else {
        divisor++;
      }
    }
    return factors;
  }

  // 주어진 number 범위 내에서 반복
  for (let i = 2; i <= number; i++) {
    // 소인수 분해를 통해 약수 개수를 구함
    const primeFactors = primeFactorization(i);
    let count = 1;

    // 구한 소인수를 통해 약수의 개수를 구함
    for (const factor in primeFactors) {
      count *= primeFactors[factor] + 1;
    }

    // 약수의 개수가 limit을 초과하면 power 값으로 치환
    count = count > limit ? power : count;
    // 누적 약수 개수를 answer에 더함
    answer += count;
  }
  return answer;
}

---

 

1차 개선 - 로직 시간 개선해보기(소인수분해 -> 에라토스테네스의 체)

그렇게 소인수분해 함수를 분리하여 로직 시간을 개선하였지만

그럼에도 보이는 것과 같이 오랜 시간이 걸리는 케이스들이 있었습니다.

 

그래서 이런 문제가 나올 때마다 사용하는 친숙한 용어가 있죠.

이제는 많이 알려지고, 사용되고 있는 '에라토스테네스의 체' 입니다.

 

에라토스테네스의 체?

1. 에라토스테네스의 체를 사용하여 한 번에 모든 소수를 구합니다.
2. 각 소수의 거듭제곱수를 반복하며 약수의 개수를 구합니다.

한 번에 모든 소수를 구해서 저장하는 특징은 DP(Dynamic Programming)에서 사용되는 로직이죠.

이렇게 소수를 여러 번 구해야하는 문제에서 시간 초과 없이 풀 수 있는 최적의 방법인 것 같습니다.

 

그래서 이런 알고리즘 구성을 가지고 있는 에라토스테네스의 체를 이용하면

아래와 같이 로직 가동 시간이 엄청나게 감소한다는 사실을 알 수 있습니다.

초기 정답 코드 결과 / 에라토스테네스의 체 사용 후

function solution(number, limit, power) {
    let answer = 1;

    // 에라토스테네스의 체를 이용하여 소수 구하기
    function sieveOfEratosthenes(num) {
        const primes = [];
        const isPrime = Array(num + 1).fill(true);

        // 0과 1은 소수가 아니므로 false로 설정
        isPrime[0] = isPrime[1] = false;

        // 2부터 시작하여 num 범위 내의 소수를 구함
        for (let i = 2; i * i <= num; i++) {
            if (isPrime[i]) {
                primes.push(i);

                // 소수의 배수들을 소수가 아닌 것으로 표시
                for (let j = i * i; j <= num; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        return primes;
    }

    // 주어진 범위 내의 모든 소수를 구함
    const primes = sieveOfEratosthenes(number);

    // 각 숫자에 대해 소인수 분해를 수행하고 약수의 개수를 구함
    for (let i = 2; i <= number; i++) {
        let count = 1;
        let num = i;

        // 소수 목록을 순회하며 소인수 분해를 수행
        for (const prime of primes) {
            // 소수의 제곱이 num보다 클 경우 루프를 빠져나옴
            if (prime * prime > num) {
                break;
            }

            let exponent = 0;
            // num이 소수로 나누어 떨어질 때까지 반복
            while (num % prime === 0) {
                exponent++;
                num /= prime;
            }

            // 지수가 0이 아니라면 약수의 개수를 업데이트
            if (exponent !== 0) {
                count *= (exponent + 1);
            }
        }

        // 소인수 분해 후 남은 숫자가 1이 아니라면
        // 마지막 소인수에 대해 약수의 개수를 업데이트
        if (num !== 1) {
            count *= 2;
        }

        // 약수의 개수가 limit을 초과하면 power 값으로 치환
        count = count > limit ? power : count;
        // 누적 약수 개수를 answer에 더함
        answer += count;
    }
    return answer;
}

 

---

 

2차 개선 - 가독성 향상 작업

전체적으로 코드를 다듬으면서 JavaScript의 문법적인 특징을 활용하여 코드의 가독성을 향상시켰습니다.

추가로 코드 로직의 깊이를 2보다 깊어지지 않게하는 작업도 함께 진행하였습니다.

왼쪽(1차 개선)과 오른쪽(2차 개선)의 차이가 거의 없다.

가독성 향상 작업이 만족스럽게 진행된 것 같네요!

function solution(number, limit, power) {
  let answer = 1;

  // 에라토스테네스의 체를 이용하여 소수 구하기
  function sieveOfEratosthenes(num) {
    const primes = [];
    const isPrime = Array(num + 1).fill(true);

    // 0과 1은 소수가 아니므로 false로 설정
    isPrime[0] = isPrime[1] = false;

    for (let i = 2; i * i <= num; i++) {
      // i가 소수일 경우 primes 배열에 추가
      if (isPrime[i]) primes.push(i);
      // i가 소수가 아닐 경우 다음 숫자로 건너뜀
      else continue;

      // i의 배수를 소수가 아닌 것으로 표시
      for (let j = i * i; j <= num; j += i) {
        isPrime[j] = false;
      }
    }
    return primes;
  }

  // 주어진 범위 내의 모든 소수를 구함
  const primes = sieveOfEratosthenes(number);

  // 각 숫자에 대해 소인수 분해를 수행하고 약수의 개수를 구함
  for (let i = 2; i <= number; i++) {
    let count = 1;
    let num = i;

    // 소수 목록을 순회하며 소인수 분해를 수행
    for (const prime of primes) {
      // 소수의 제곱이 num보다 클 경우 루프를 빠져나옴
      if (prime * prime > num) break;

      let exponent = 0;
      // num이 소수로 나누어 떨어질 때까지 반복
      while (num % prime === 0) {
        exponent++;
        num /= prime;
      }

      // 지수가 0이 아니라면 약수의 개수를 업데이트
      if (exponent !== 0) count *= exponent + 1;
    }

    // 소인수 분해 후 남은 숫자가 1이 아니라면
    // 마지막 소인수에 대해 약수의 개수를 업데이트
    if (num !== 1) count *= 2;

    // 약수의 개수가 limit을 초과하면 power 값으로 치환하고 누적
    answer += count > limit ? power : count;
  }
  return answer;
}

 

---

End