[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(\sqrt{N})$
제곱근까지 탐색	$O(\sqrt{N} \log N)$	$O(\sqrt{N})$

($N$ = 입력값 n. 두 풀이 모두 반환하는 약수가 최대 $2\sqrt{N}$개)

---

3. 코드

풀이 1: 완전 탐색 [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);
            }
        }

        return list.stream().mapToInt(Integer::intValue).sorted().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;
}

import math


def solution(n):
    st = set()

    for i in range(1, math.isqrt(n) + 1):
        if n % i == 0:
            st.add(i)
            st.add(n // i)

    return sorted(st)

---