프로그래머스 Lv.1 | 기사단원의 무기 (JavaScript)

프로그래머스

 

💡 접근 방식:
1. 1부터 number까지의 배열을 만들고, 각 숫자의 약수의 개수를 구한다.
2. limit보다 큰 요소가 있는지 체크한 후, 있다면 해당 요소를 power로 갈음한다.
3. reduce로 최종 합계를 구한다.

 
이 문제의 핵심은 '약수의 개수를 구하기'라고 생각한다. 약수란 모름지기 나눠서 떨어지는 수가 있느냐가 관건이기에 나머지가 0이 되는 수를 찾아야 한다. 모듈로(%) 연산을 쓰면 간단히 해결할 수 있다. 
 
약수를 구하는 3가지 방식이 있다. 
 
첫번째: 1부터 number까지 모든 수를 나눠서 약수 구하기 - 시간 복잡도 O(n)
두번째: 주어진 수의 절반을 대상으로만 확인 - 시간 복잡도 O(n/2)이지만 O(n)과 큰 차이가 없다. 
세번째: 제곱근(Math.sqrt) 사용 - 시간 복잡도 O(log n)
 
처음에는 두번째 방식을 사용해 문제를 풀었다. 약수는 자기 자신을 제외하고는 n/2보다 클 수 없기 때문에 절반 값까지만 체크한 후, 자기 자신을 더한다.

arr.map((n) => {
    let count = 0;

    for (let i = 0; i <= n / 2; i++) {
      if (n % i === 0) count++;
    }
    return count + 1;
  });

 
전체 문제 풀이는 다음과 같다. 

function solution(number, limit, power) {
  const arr = Array.from({ length: number }, (_, i) => i + 1);

  return arr
    .map((n) => {
      let count = 0;

      for (let i = 0; i <= n / 2; i++) {
        if (n % i === 0) count++;
      }
      // count + 1 : 자기 자신 포함
      return count + 1 > limit ? power : count + 1;
    })
    .reduce((a, c) => a + c, 0);
}

 
이렇게 코드를 작성하고 제출을 해보니 통과율이 66%다. 총 27개의 테스트 중에서 테스트 11~16, 18, 24~25를 통과하지 못하는데 시간 초과로 뜬다. 프로그래머스는 테스트 코드를 공개하지 않지만 시간 초과라고 뜨는 걸 봐서 시간 복잡도를 낮춰야 한다. 
 
제곱근을 사용할 때의 핵심은 다음과 같다. 

1) 제곱근 이하의 숫자 중에 n을 i로 나눈 나머지의 값이 0이면
2) i는 n의 약수이다.
3) n을 i로 나눈 값도 n의 약수이다.

출처: [알고리즘] 약수 구하기 기본 & 제곱근(Math.sqrt)
 
 
예를 들어보자. 
 
100의 제곱근은 10이다. 
10의 약수는 [1, 2, 4, 5, 10] 이다. 
이제 100을 10의 약수로 나눠보자. 
* 100 / 1 = 100
* 100 / 2 = 50
* 100 / 4 = 25
* 100 / 5 = 20
* 100 / 10 = 10 
[10, 20, 25, 50, 100] 도 10의 약수이다. 
(주의: 10이 중복됨) 
 
중복 제거를 하는 여러 가지 방법이 있지만 Set을 사용해서 코드를 작성해 보기로 한다. Set은 중복을 허용하지 않은 값을 모아놓기 때문에 값의 유일무이함을 확인하는데 최적화되어 있다. 첫번째 풀이에서 약수를 구하는 부분만 코드를 수정하니 모든 테스트를 통과했다. 
 

function solution(number, limit, power) {
  const arr = Array.from({ length: number }, (_, i) => i + 1);

  return arr
    .map((n) => {
      const divisors = new Set();

      for (let i = 1; i <= Math.sqrt(n); i++) {
        // set.add는 체이닝이 가능함. 아래의 코드와 동일한 코드
        if (n % i === 0) divisors.add(i).add(n / i);

        // if (n % i === 0) {
        //   divisors.add(i);
        //   divisors.add(n / i);
        // }
      }

      const count = [...divisors].length;
      return count > limit ? power : count;
    })
    .reduce((a, c) => a + c, 0);
}

 
코딩 테스트를 풀 때 이렇게 시간 복잡도를 생각해서 풀어야 하는 문제들이 종종 있다. 사실 프론트엔드에서는 이런 시간 복잡도를 고려하기보다는 렌더링 최적화에 대한 고민을 더 많이 하게 되긴 한다. 그래서 코딩 테스트 문제 풀이는 역시 수학의 정석 푸는 느낌...
 
 
+) 1~N까지 숫자를 요소로 하는 배열을 만드는 방법은 위의 솔루션에서는 Array.from()을 사용했지만, .fill() 메소드를 사용해도 된다.  
(참고: 배열 초기화: Array.fill()과 Array.from()의 차이)

const arr = new Array(number).fill().map((_, i) => i + 1)