보통수학복잡도

약수 구하기

양의 정수 n이 주어져요. n의 모든 약수를 오름차순 배열로 반환해요.

1부터 n까지 하나씩 나눠보면 O(n)이에요. n이 10억이면 이 방법은 제한 시간을 넘겨요.

약수는 항상 짝을 이뤄요. i가 n의 약수라면 n / i도 약수이므로, i * i ≤ n 인 범위만 훑고 짝을 함께 담으면 O(√n)에 끝나요. 10억이 3만 번 남짓으로 줄어들어요.

예시

예시 1

입력: n = 12
출력: [1, 2, 3, 4, 6, 12]

예시 2

입력: n = 36
출력: [1, 2, 3, 4, 6, 9, 12, 18, 36]
설명: 6 × 6 = 36 이므로 6은 짝이 자기 자신이에요. 두 번 담지 않도록 주의해요.

예시 3

입력: n = 1
출력: [1]

제한 사항

1 ≤ n ≤ 1,000,000,000

i * i <= n 조건으로 돌면서 i와 n / i를 각각 모으고, 마지막에 합쳐서 정렬해요. 정렬 없이 하려면 작은 쪽은 앞에서부터 담고 큰 쪽은 따로 모았다가 뒤집어 붙이면 돼요. i * i === n 인 경우를 두 번 담지 않도록 해요.

javascript
Copy code
function divisors(n) {
  const small = [];
  const large = [];
  for (let i = 1; i * i <= n; i++) {
    if (n % i !== 0) continue;
    small.push(i);
    if (i !== n / i) large.push(n / i);
  }
  large.reverse();
  return small.concat(large);
}

이전 문제최솟값과 최댓값

다음 문제배열의 합과 최댓값

예시 테스트만 실행 (Cmd/Ctrl+Enter)

숨김 테스트까지 채점 (Cmd/Ctrl+Shift+Enter)

에디터를 불러오고 있어요…

코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.