[Algorithm] 약수 구하기 (Kotlin)

모두 알고 있겠지만 약수의 사전적 정의는 아래와 같다.

 

어떤 정수를 나머지 없이 나눌 수 있는 정수를 원래의 수에 대해 이르는 말. 예를 들어 3은 6의 약수다

 

사전적 정의가 너무 어렵다. 위키백과의 정의는 좀 더 알기 쉽다.

 

https://ko.wikipedia.org/wiki/%EC%95%BD%EC%88%98

약수 - 위키백과, 우리 모두의 백과사전

약수 또는 인수는 어떤 수를 나눠떨어지게 하는 수를 말한다. 12의 모든 양의 약수는 1, 2, 3, 4, 6, 12다

 

위키백과의 예시인 12를 보면 12를 1~12까지의 정수 중 하나의 숫자로 나눴을 때 나머지가 0이 되는 숫자를 구하려면, 1부터 12까지 모두 나눠서 나머지가 어떤지 확인하는 것이다.

 

• 12 % 1 = 0
• 12 % 2 = 0
• 12 % 3 = 0
• 12 % 4 = 0
• 12 % 5 = 2
• 12 % 6 = 0
• 12 % 7 = 5
• 12 % 8 = 4
• 12 % 9 = 3
• 12 % 10 = 2
• 12 % 11 = 1
• 12 % 12 = 0

 

이래서 12의 약수는 1, 2, 3, 4, 6, 12다. 이것은 모든 경우를 탐색한 경우기 때문에 O(N)의 시간 복잡도를 갖는다고 할 수 있다. 그래서 약수를 구하라고 던져준 숫자가 억 단위를 넘어가면 시간 제한 때문에 못 풀 확률이 높다.

위의 방식을 코드로 옮기면 아래처럼 된다.

 

fun main() {
    findDivisor(12)
}

fun findDivisor(number: Int) {
    for (i in 1 .. number) {
        if (number % i == 0) {
            println("약수 : $i")
        }
    }
}

// 약수 : 1
// 약수 : 2
// 약수 : 3
// 약수 : 4
// 약수 : 6
// 약수 : 12

 

그러나 위에서 말했듯 큰 숫자가 주어졌다면 사용할 수 없다. 그럼 최적화 작업을 해야 하는데 이건 또 어떻게 하는 건가?

 

https://kbw1101.tistory.com/32

[알고리즘] 효율적으로 약수를 찾는 알고리즘

n의 약수를 구할 때는 1부터 n의 제곱근까지의 숫자만 0으로 나눠 떨어지는지 확인하면 된다. 왜 그렇게 되는 것인가? 100의 약수를 구하는 사례를 확인해보자. 제곱근까지만 구하기로 했으니 1~10사이의 수에 대해 100이 0으로 나눠떨어지는지만 보면 된다

100 % 1 = 0
100 % 2 = 0
100 % 3 = 1
100 % 4 = 0
100 % 5 = 0
100 % 6 = 4
100 % 7 = 2
100 % 8 = 4
100 % 9 = 1
100 % 10 = 0

이를 통해 100의 약수는 1, 2, 4, 5, 10을 갖는다는 걸 알게 됐다. 그 다음 100을 앞에서 구한 1, 2, 4, 5, 10으로 나눈다

100 / 1 = 100
100 / 2 = 50
100 / 4 = 25
100 / 5 = 20
100 / 10 = 10

이렇게 하면 이미 구했던 숫자들 외에 10, 20, 25, 50, 100이 추가로 구한 약수가 된다. 이제 중복을 제거하고 오름차순 정렬하면 아래처럼 100의 약수들을 구할 수 있다

1, 2, 4, 5, 10, 20, 25, 50, 100

이 경우 시간 복잡도가 O(√n)이 되므로 입력으로 10억이 들어오더라도 약 3만 번의 연산으로 약수를 구할 수 있다. 그래서 웬만한 문제에서 시간 초과가 발생하는 일은 없을 것이다

 

제곱근을 쓰면 된다는 건 알겠다. 그런데 코틀린에서 제곱근은 어떻게 구하는 건가?

kotlin.math에 포함된 sqrt()를 쓰면 구할 수 있다. 프로그래머스의 레벨 0 문제 중 아래 문제에서 sqrt()를 써서 이 함수의 설명 원문 링크를 인용했었다.

 

https://onlyfor-me-blog.tistory.com/626

[Algorithm] 프로그래머스 - 제곱수 판별하기 (Kotlin)

 

이제 sqrt()를 써서 100의 모든 약수들을 구한다.

 

import kotlin.math.sqrt

fun main() {
    findDivisor(100)
}

fun findDivisor(number: Int) {
    val sqrt = sqrt(number.toDouble())
    val result = arrayListOf<Int>()
    for (i in 1 .. sqrt.toInt()) {
        if (number % i == 0) {
            result.add(i)
            if (number / i != i) {
                result.add(number / i)
            }
        }
    }

    println("${number}의 모든 약수 : ${result.sorted()}")
}

// 100의 모든 약수 : [1, 2, 4, 5, 10, 20, 25, 50, 100]

 

조건을 2개 걸었다. 맨 위의 코드처럼 100을 1~100까지의 모든 숫자로 나눴을 때 나머지가 없는지 확인하고, 2번째로 100을 1~100까지의 숫자 중 하나로 나눠서 그 숫자가 아닌지 확인한다. 이렇게 하면 리스트에 100의 약수들만 들어가게 되고 정렬해서 출력하면 모든 약수를 구할 수 있다.

 

그냥 sqrt() 하나 추가한 건데 시간 차이가 뭐 얼마나 많이 나냐 생각될 수도 있다. 그래서 저 함수들 각각에 10억을 넣고 시간이 얼마나 걸리는지 재봤다.

 

import kotlin.math.sqrt

fun main() {
    findDivisor(1_000_000_000)
    findDivisor2(1_000_000_000)
}

fun findDivisor(number: Int) {
    val startTime = System.currentTimeMillis()
    val sqrt = sqrt(number.toDouble())
    val result = arrayListOf<Int>()
    for (i in 1 .. sqrt.toInt()) {
        if (number % i == 0) {
            result.add(i)
            if (number / i != i) {
                result.add(number / i)
            }
        }
    }

    val endTime = System.currentTimeMillis()
    val totalTime = endTime - startTime
    println("${number}의 모든 약수 : ${result.sorted()}")
    println("걸린 시간 : $totalTime")
}

fun findDivisor2(number: Int) {
    val startTime = System.currentTimeMillis()
    val sqrt = sqrt(number.toDouble())
    val result = arrayListOf<Int>()
    for (i in 1 .. number) {
        if (number % i == 0) {
            result.add(i)
        }
    }

    val endTime = System.currentTimeMillis()
    val totalTime = endTime - startTime
    println("${number}의 모든 약수? : ${result.sorted()}")
    println("걸린 시간? : $totalTime")
}

// 1000000000의 모든 약수 : [1, 2, 4, 5, 8, 10, ..., 1000000000]
// 걸린 시간 : 0
// // 1000000000의 모든 약수? : [1, 2, 4, 5, 8, 10, ..., 1000000000]
// 걸린 시간? : 1297

 

sqrt()를 쓰면 보통 0이 출력되는데 아주 가끔 1이 출력되기도 한다. 반면 sqrt()를 쓰지 않은 함수는 기본 1초 이상 걸리는 걸 볼 수 있다. 위의 소스코드를 복붙해서 실행해보면 금세 알 수 있다.

이제 약수를 구할 때 큰 숫자가 주어지면 sqrt() 사용을 고려해 보는 게 좋을 것 같다. 만약 쓴다면 import문은 잊지 말고 꼭 써줘야 한다.