프로그레머스/Lv0/약수 구하기

문제 설명

정수 n이 매개변수로 주어질 때, n의 약수를 오름차순으로 담은 배열을 return하도록 solution 함수를 완성해주세요.

제한사항

• 1 ≤ n ≤ 10,000

입출력예

n	result
24	[1, 2, 3, 4, 6, 8, 12, 24]
29	[1, 29]

---

이 문제를 풀기 이전에 비슷한 유형의 문제를 푼적이 있었기에 처음부터 최적화된 풀이를 만들기로 했다.

약수는 항상 대칭 구조 이기 때문에 ex) 4가 24의 약수라면 4X6=24 이므로 6또한 약수이다.

반복문의 실행 범위를 √n 까지만 실행되도록 했다. 그렇게 해서 나온 코드는

---

function solution(n) {
    let answer = [];
    for(let i = 1; i <= Math.sqrt(n); i++){
        if(n%i === 0){
            i === Math.sqrt(n) ? answer.push(i) : answer.push(i,n/i);
        }
    }
    return answer.sort((a,b) => a-b);
}

처음부터 배열 순서에 맞춰서 넣어 줄 수 있지만 그렇게 한다면 한 요소를 삽입 할 때 마다 배열을 순회해서 연산속도가 증가하기 때문에 마지막에 sort()로 한번만 정리해주었다. 또한, √n(Math.sqrt(n))의 제곱근의 경우 1개만 들어가야 하므로 해당 부분을 예외 처리해주었다.

 이외에 다른 분들 풀이를 보고 참고 할 만한 풀이들이 있었다.

---

function solution(n) {
    let s = new Set();
    for (let i = 1; i <= Math.sqrt(n); i++) {
        if (n%i === 0) {
            s.add(i);
            s.add(n/i);
        }
    }
    return [...s].sort((a,b)=>a-b);
}

Set.add라는 재미있는 메소드였다. Set 객체에만 사용가능 하며 Set의 속성에 맞게 중복되는 요소는 추가 되지 않는다. 이를 이용해 제곱근 문제를 해결 할 수 있다. 다만, 범용성이 다소 떨어지는 단점이있다. 특정 상황에서 참고 할 만한 풀이이다.

https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Set/add

Set.prototype.add() - JavaScript | MDN

두 번째로 관심 있게 보았던 풀이는 미리 1~n 까지의 배열을 만들고 필터링을 적용한 풀이였다.

function solution(n) {
    return Array(n).fill(0).map((v, index) => v+index+1).filter((v) => n%v===0);
}

아이디어가 좋았던 것 같다. fill() 메소드를 적용해본적이 없어서 생각을 못 하고 있었다. 다만, 1부터 n까지 전부 조회하는 과정이 두 번있기 때문에 제곱근으로 범위를 제한한 풀이와 다르게 연산속도가 더 느리고, n이 커질 수록 그 차이 가 더 벌어지는 문제가 있다.

 

약수 관련 문제는 알고리즘 문제에서 자주 나오는 패턴이라 생각해서 제곱근으로 시간 절약을 한다는 점을 기억해야 한다.