Swift 로 해결하기

스위프트로 알고리즘 문제 해결하기

1. 문제

N 이하의 자연수들의 약수의 개수를 출력하라.

2. 조건

N 은 1 이상, 5만 이하의 자연수이다.

3. 내가 생각한 풀이

간단히 모든 약수의 개수를 구하는 방식으로 생각했다.

var i: Int = 1
while i * i < n { i += 1 }

로 자연수 n의 제곱근 보다 작은 자연수를 구하고 ( 나름 1부터 n 까지 모두 돌지 않은, 시간복잡도를 줄인 코드였다)

if i * i == n { count -= 1 }
var j : Int = 1
while j <= i { 
	if n % j == 0 { count += 2 }
}

로 하나하나 모두 약수를 구해서 출력하는 원시적인 방법을 택함

4. 문제점

자연수 n 이 30000이 되었을 때
i 를 찾기위해 100이 넘는 숫자까지 한번 돌고,
j 를 모든 i 까지 돌려야 하는 코드이기 때문에
( i 가 100이 되면, j는 1 부터 100까지를 모두 더한 5500번을 돌게된다.)
숫자가 커질수록 런 타임에러가 뜰 확률이 높아진다.

5. 코드 개선

func solution(_ n : Int) {
    var cnt = Array(repeating: 0, count: n+1)
    var j: Int = 1

    for i in 1...n+1 {
        j = i
        while j < n+1 {
            cnt[j] += 1
            j += i
        }
    }
    print(cnt[cnt.startIndex+1..<cnt.endIndex])
}

n+1개의 0으로 가득 찬 cnt: [Int] 를 만든다.
i = 1 부터, 모든 1의 배수에 cnt += 1 을 해준다.
i = 2 부터, 모든 2의 배수에 cnt += 1 을 해준다.
i = 3 부터, 모든 3의 배수에 cnt += 1 을 해준다.
...

n = 30000 이었다면
i = 1 일 때, 30000
i = 2 일 때, 15000
i = 3 일 때, 10000
....

코드가 숫자를 탐색하는 양이 확실히 줄어들었음을 확인 할 수 있다.