[Level0] 약수 구하기

문제

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

 

제한사항

 

• 1 ≤ n ≤ 10,000

 

입출력 예시 

• 예시1

• 입력 : n = 24
• 출력 :[1, 2, 3, 4, 6, 8, 12, 24]
• 설명 : 24의 약수를 오름차순으로 담은 배열 [1, 2, 3, 4, 6, 8, 12, 24]를 return합니다.

 

• 예시2

• 입력 : n = 29
• 출력 :[1, 29]
• 설명 : 29의 약수를 오름차순으로 담은 배열 [1, 29]를 return합니다.

 

---

내 풀이

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


console.log(solution(24));
console.log(solution(29));

 

• 시간 복잡도 : O(n)
• 설명 : 이 코드는 주어진 수 n에 대해 1부터 n까지의 자연수 중에서 n의 약수를 찾아내는 역할을 한다.
  Array(n).fill(1)은 길이가 n이고 모든 요소가 1로 채워진 배열을 생성한다.
  map((v, i) => v + i)를 사용하여 배열의 각 요소에 현재 인덱스 i를 더해준다. 이렇게 하면 1부터 n까지의 자연수 배열이 만들어진다.
  filter((_, idx) => n % (idx + 1) === 0)를 사용하여 현재 인덱스 idx에 대해 n을 (idx + 1)로 나누어 떨어지는 경우만을 걸러낸다. 이렇게 하면 n의 약수만 남는다.
  
  Array(n).fill(1).map((v, i) => v + i) 부분의 시간 복잡도는 O(n)이다. 배열을 생성하고 초기화하는 데 선형 시간이 소요된다.
  filter((_, idx) => n % (idx + 1) === 0) 부분은 O(n)이다. 생성된 배열을 순회하면서 n을 나누어 떨어지는지 확인한다.
  따라서 전체 코드의 시간 복잡도는 O(n)이다.
  
  
• 느낀점 : 
  최대한 코드를 간결하고, 주어진 수 n에 대한 약수를 찾는 목적에 맞게 작성하려 했다. 그러나 채점 후 Array(n)을 사용하여 배열을 초기화하고, 나중에 map 및 filter를 사용하는 부분에서 메모리를 많이 소비할 수 있다는 것을 알았다. 이 코드는 주어진 범위에 따라 선형 시간에 처리되는 알고리즘이다. 입력 범위가 적당하다면 효율적으로 동작할 것이다. 그러나 입력 범위가 매우 크다면 선형 시간으로도 부담이 될 수 있으니 이점을 고려하여 사용하는 것이 좋다. 

 

---

해결 방법

function solution(n) {
    let result = [];
    for (let i = 1; i <= Math.sqrt(n); i++) {
        if(n % i === 0){
            result.push(i);

            if(i !== n/i) result.push(n/i);
        } 
    }
    return result.sort((a,b) => a - b);
}

 

• 시간 복잡도 : O(sqrt(n))
• 설명 : 이 코드는 for 루프가 Math.sqrt(n)까지 반복한다. 각 반복에서 주어진 수 n을 현재 반복 변수 i로 나누어 나머지가 0이면, i는 n의 약수이므로 결과 배열에 추가되고, i와 n/i 중 하나가 Math.sqrt(n)와 같지 않은 경우에만 두 번째 약수도 추가된다.
  이 코드는 1부터 Math.sqrt(n)까지의 수를 반복하며, 현재 수 i가 n의 약수인지 확인한다. 만약 약수라면, result 배열에 i를 추가하고, i와 n/i 중 하나가 Math.sqrt(n)와 같지 않은 경우에만 두 번째 약수도 추가한다.
  이 코드는 주어진 문제에 대해 적절한 방식으로 약수를 찾고, 중복을 피하여 정렬까지 수행하고 있으므로 효율적인 코드이다. 약수를 찾는 과정에서 불필요한 반복을 줄이고 있으며, 정렬을 통해 결과를 가독성 있게 반환한다.