문제: 정수 n을 입력받아 n의 약수를 모두 더한 값을 리턴하는 함수, solution을 완성해 주세요.
문제 풀어보기: https://school.programmers.co.kr/learn/courses/30/lessons/12928
풀이 보기
더보기
function solution(n) {
let nums = [];
for(let i = 1; i <= n; i++) {
if(n % i === 0) nums.push(i);
}
let sum = nums.reduce((acc, curr) =>
acc + curr, 0);
return sum;
}
이 문제는 너무 쉽지만 단순히 푸는 것이 아닌 시간복잡도를 고려해야 한다.
위의 코드도 정답이긴 하지만, 만약 n이 엄청 큰 숫자라면 1부터 n까지 반복을 해야 하기 때문에 시간복잡도가 커지게 된다.
나는 reduce를 사용하고 싶어서 저렇게 했지만 더 간단하게 작성할 수도 있다!
function solution(n) {
let sum = 0;
for (let i = 1; i <= Math.sqrt(n); i++) {
if (n % i === 0) {
sum += i;
if (i !== n / i) sum += n / i;
}
}
return sum;
}
이 코드는 시간복잡도를 개선한 코드이다.
약수는 짝을 이루는 특징이 있기 때문에 그 특징을 활용하면 된다!
만약 i가 n의 약수일 경우, n / i도 약수이기 때문에 제곱근을 활용해서 i의 범위를 좁혀준다.
따라서 위의 코드처럼 실행한다면 먼저 1부터 제곱근까지의 수에서 약수를 탐색하여 더해주고,
탐색한 약수의 짝꿍을 찾아서 그 수도 더해준다.
여기서 i가 중복되지 않게 i !== n / i 조건도 넣어줘야 한다.
n이 큰 수가 아니라는 가정일 때는 첫 번째 코드를 사용하는 것이 좋을 수도 있을 것 같다.
'코딩 테스트' 카테고리의 다른 글
[프로그래머스 Level 1] 평균 구하기 (0) | 2025.03.10 |
---|---|
[프로그래머스 Level 1] 나누어 떨어지는 숫자 배열 (0) | 2025.03.07 |
[프로그래머스 Level 1] 짝수와 홀수 (0) | 2025.03.07 |
[프로그래머스 Level 1] 나머지가 1이 되는 수 찾기 (0) | 2025.03.06 |
[프로그래머스 Level 1] 과일 장수 (0) | 2025.03.06 |