프로그래머스 - 기사단원의 무기

https://school.programmers.co.kr/learn/courses/30/lessons/136798

프로그래머스

 

문제 자체는 간단하다.

천천히 읽으면 무슨 말인지 이해하는데 어렵지 않다.

 

이 문제의 핵심은 아래인데

각 기사는 자신의 기사 번호의 약수 개수에 해당하는 공격력을 가진 무기를 구매하려 합니다. 단, 이웃나라와의 협약에 의해 공격력의 제한수치를 정하고, 제한수치보다 큰 공격력을 가진 무기를 구매해야 하는 기사는 협약기관에서 정한 공격력을 가지는 무기를 구매해야 합니다. 예를 들어, 15번으로 지정된 기사단원은 15의 약수가 1, 3, 5, 15로 4개 이므로, 공격력이 4인 무기를 구매합니다.

 

즉 약수의 갯수를 구해야한다.

그리고 이 문제에서 주어질 수 있는 기사단원의 넘버는 1 <= number <= 100,000 이다.

숫자가 크기 때문에 약수를 구하는 코드의 시간이 중요해진다.

 

약수를 찾을 때 아래의 방식으로 시간 단축을 할 수 있다.
"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

그렇게 되면, 이미 구했던 1, 2, 4, 5, 10 외에 100, 50, 25, 20, 10이 추가로 구해진 약수가 된다는 것을 알 수 있다.
이제, 중복을 제거하고 오름차순으로 순서를 정렬하자.
그럼 다음과 같이, 100의 약수를 모두 구할 수 있다.

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

이 경우에는 시간 복잡도가 O(√N)이 되므로, 10억의 입력이 들어온다해도, 약 3만번의 연산으로 약수를 구할 수 있다.

 

이 방법을 생각하고 코드를 짜면 시간초과 없이 문제를 완료할 수 있다.

import kotlin.math.sqrt
class Solution {
    fun solution(number: Int, limit: Int, power: Int): Int {
        var answer: Int = 0
        for(i in 1 .. number){
            var resultPw = findDivisor(i)
            if(resultPw > limit){
                answer+= power
            }else{
                answer+= resultPw
            }
        }
        
        return answer
    }
    
    fun findDivisor(number: Int) : 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)
                }
            }
        }
        return result.size
    }
}

 

뚝딱