[level 1] 약수의 합

2022. 1. 15. 09:56

문제

풀이 코드

function solution(n) {
  if (n === 0) {
    return 0;
  }

  let prime = [];

  if (n % Math.sqrt(n) === 0) {
    prime.push(Math.sqrt(n));
  }
  for (let i = 1; i < Math.sqrt(n); i++) {
    if (n % i === 0) {
      prime.push(i);
      prime.push(n / i);
    }
  }
  return prime.reduce((sum, num) => sum + num, 0);
}

풀이 과정

약수를 구하는 문제.. 아.. 확실히 PS 문제를 풀다보니까 42Seoul 이 도움이 된다.

해당 문제 그냥 n 까지 1씩 더해서 다~~ 구했었는데

42서울에서 시간초과가 나서 고민을 많이 하다 발견한게 제곱근을 이용한 풀이였다.

제곱근까지만 구하고, 구해진 약수와, n 을 약수로 나눈 몫, 그리고 제곱근 만 구해주면 시간적 측면에서 엄청난 단축을 할수 있다.

예를들어.. 3000 이라고 치면

1, 2, 3, 4, 5,,...100,101,102...2000,2001,2002...2999,3000

이렇게 하나하나 나누어 가며 나머지가 0인놈들을 선별해야 하지만

제곱근을 이용하면 54 까지만 비교하고,

54까지의 약수들과, N을 해당 약수로 나눴을때 몫, 그리고 N을 해당 제곱근으로 나눴을때 나머지가 0이라면 이 값들만 계산하면 된다

따라서 시간복잡도 성능 업업!!

이렇게 약수들을 더해 배열에 넣고,

reduce 고차함수를 통하여 약수들을 싹 더해줬다

다른사람의 코드

function solution(n, a=0, b=0) {
    return n<=a/2?b:solution(n,a+1,b+=n%a?0:a);
}

3항 연산자를 중첩으로 이용하고, 재귀함수를 이용하려 푸셨다.

근데 가독성이 너무 떨어져서 굳이 이렇게 풀어야 하나 싶다.

한줄로 깔끔하게 짠건 참신하다는 생각이 든다!

Chikong