[Swift 알고리즘] 모두의 약수 (시간제한 1초)

자연수 N이 입력되면 1부터 N까지의 각 숫자들의 약수의 개수를 순서대로 출력하는 프로그램을 작성하세요.

자연수 N (5<=N<=50,000)

입력 : 8

출력 : 1 2 2 3 2 4 2 4

 

시간복잡도 비교해보기 

 

1. 1~N 까지 & 1~i 까지 이중 for문 다 돌면서 약수인지 아닌지 하나하나 다 확인하는 방법

: 시간복잡도 O(n^2)에 수렴

let input = readLine()!
let N = Int(input)!
print(divisor(N))

func divisor(_ N: Int) -> String {
    var result = Array(repeating: 0, count: N)
    for i in 1...N {
        for j in 1...i {
            if i % j == 0 {
                result[i-1] += 1
            }
        }
    }
    return result.map{ String($0) }.joined(separator: " ")
}

 

2. 1~N 까지 i의 배수들에 +1씩 해주는 방법

: 시간복잡도 O(nlogn) 까지는 아니더라도 이에 가까움. 

let input = readLine()!
let N = Int(input)!
print(divisor(N))

func divisor(_ N: Int) -> String {
    var result = Array(repeating: 0, count: N)
    for i in 1...N {
        for j in stride(from: i, through: N, by: i) {
            result[j-1] += 1
        }
    }
    return result.map{ String($0) }.joined(separator: " ")
}

 

속도 비교 테스트

입력값	1번 : O(n^2)	2번 : O(nlogn)
8	0.001959085464477539	0.0020400285720825195
500	0.032768964767456055	0.005385994911193848
10000	11.054525971412659	0.03326690196990967
50000	측정불가	0.07549607753753662

O(nlogn)으로 풀면 입력값이 50000을 넘어가도 수행 시간이 1초를 넘지 않지만,

O(n^2)으로 풀면 입력값이 커질수록 수행 시간도 급격하게 늘어나는 것을 확인할 수 있었다. 

 

속도 차이 엄청나구만,, 신기하다 ㅎㅎ