[BOJ] 백준 2501 약수 구하기 (Swift)

문제

https://www.acmicpc.net/problem/2501

2501번: 약수 구하기

풀이

n의 약수를 확인하는 방법중 1 ~ n 까지로 나누어서 나누어 떨어진다면 약수인 것으로 확인할 수 있습니다.
시간복잡도는 $O(n)$ 입니다.

더 빠르게 약수인 수를 판단할 수는 없을까요?
단순히 1부터 n의 제곱근 까지만 확인하는 방법이 있습니다.
1 ~ $\sqrt{n}$ 까지 수를 확인한 후, 나누어 떨어진다면 그 수가 약수일 것이고, n / i의 수도 약수일 것입니다.

예를 들어 20이란 수가 있다면, 20의 제곱근은 약 4.4로 1부터 4까지의 수를 확인해봅시다.
20을 4로 나누면 나누어 떨어지고, 20 / 4 = 5 입니다.
즉, 4 * 5로 20이라는 수를 만들 수 있습니다.

25같은 경우는 5 * 5 이기 때문에 5가 중복이 되기 때문에
중복제거를 위해 Set 자료형을 사용하였고, 다시 Array로 만들어주어 정렬해주었습니다.

그 이후 Array의 크기가 k보다 작다면 0을 출력해주고, 작지 않다면 k-1 번 인덱스의 약수를 출력해주면 끝 입니다.

소스코드

후기

n이 10,000 이하 이기 때문에 $O(n)$의 방식으로 풀어도 무방하지만,
n이 커진다면 풀 수 없기 때문에 약수를 효율적으로 구하는 알고리즘을 사용했습니다.

시간복잡도를 줄일 수 있는 방법에 대해 알아두면 좋을 것 같습니다.