[Programmers] #120897 - 약수 구하기 [Java][C++][Python]

문제 링크

---

1. 아이디어

n의 약수를 오름차순으로 모으는 문제다.

가장 단순한 방법은 1부터 n까지 모든 정수로 n을 나눠 나누어떨어지는지 확인하는 것이다. 작은 수부터 순서대로 훑으므로 결과는 그대로 오름차순이 된다.

약수는 $\sqrt{N}$을 기준으로 쌍을 이룬다 — i가 n의 약수면 n / i도 약수다. 따라서 i를 1부터 $\sqrt{N}$까지만 순회하며 i와 n / i를 함께 모으면 절반 이하의 나눗셈으로 같은 결과를 얻는다. i와 n / i가 같은 경우(n이 완전제곱수이고 i가 그 제곱근일 때)엔 같은 약수가 중복으로 담기지 않도록 한 번만 넣고, 약수를 순서 없이 모으므로 마지막에 정렬한다.

---

2. 복잡도

접근	시간	공간
완전탐색	$O(N)$	$O(D)$
약수의 대칭성	$O(\sqrt{N} + D \log D)$	$O(D)$

($N$ = 입력값 n, $D$ = n의 약수의 개수)

---

3. 코드

풀이: 완전탐색 [Java][C++][Python]

import java.util.*;

class Solution {
    public int[] solution(int n) {
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            if (n % i == 0) list.add(i);
        }

        return list.stream().mapToInt(Integer::intValue).toArray();
    }
}

#include <bits/stdc++.h>
using namespace std;

vector<int> solution(int n) {
    vector<int> v;
    for (int i = 1; i <= n; i++) {
        if (n % i == 0) v.push_back(i);
    }

    return v;
}

def solution(n):
    return [i for i in range(1, n + 1) if n % i == 0]

---

풀이 2: 약수의 대칭성(제곱근 최적화) [Java][C++][Python]

import java.util.*;

class Solution {
    public int[] solution(int n) {
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i * i <= n; i++) {
            if (n % i == 0) {
                list.add(i);
                if (i != n / i) list.add(n / i);
            }
        }
        list.sort(Comparator.naturalOrder());

        return list.stream().mapToInt(Integer::intValue).toArray();
    }
}

#include <bits/stdc++.h>
using namespace std;

vector<int> solution(int n) {
    vector<int> v;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            v.push_back(i);
            if (i != n / i) v.push_back(n / i);
        }
    }
    sort(v.begin(), v.end());

    return v;
}

def solution(n):
    st = set()
    i = 1

    while i * i <= n:
        if n % i == 0:
            st.add(i)
            st.add(n // i)
        i += 1

    return sorted(st)

---