프로그래머스 알고리즘 Level 1 코틀린 기사단원의 무기

1. 첫 번째 풀이 - 과정은 맞는데 결과는 시간초과

class Solution {
    fun solution(number: Int, limit: Int, power: Int): Int = (1..number).map { i ->
        (1..i).count { i % it == 0 }
    }.map {
        if (it > limit) power else it
    }.sumOf { it }
}

일단 이걸로 돌려봄 

BUT 과정은 맞지만 시간복잡도에서 쓰레기임.

약수를 찾으려고 1부터 찾으려는 약수까지 반복문을 돌려서 count로 찾음.

이렇게 하면 O(N^2)인데 10만이면 10만 X 10만... 

시간 초과 오류와 함께 해결 하지 못함.

 

2. 두 번째 풀이 - sqrt를 활용한 최적화

import kotlin.math.sqrt

class Solution {
    fun solution(number: Int, limit: Int, power: Int): Int = (1..number).map { i ->
        val x = (1..sqrt(i.toFloat()).toInt()).filter { i % it == 0 }
        (x + x.map { i / it }).toSet().count()
    }.map {
        if(it > limit) power else it
    }.sumOf { it }
}

약수는 1부터 제곱근까지 나누어 떨어지는 수를 구하고

약수를 구하려는 수를 위에서 구한 수들로 나누어 나온 수들과 합치면

약수들이 전부 나옴.

 

이걸 이용함. 

val x = (1..sqrt(i.toFloat()).toInt()).filter { i % it == 0 }

이걸 구하면

약수를 구하려는 수의 0부터 제곱근까지 나누어 떨어지는 수들이 나옴.

5 > 5의 제곱근 2.xxx toInt > 2 > 1..2 5%1 == 0 , 5%2 != 0 > 결과 1 

윗줄과 같은 결과의 리스트가 주르르 나옴.

 

여기서 나온 수들로 다시 구하려는 수 i를 나누어줌

x.map { i / it }

 

이렇게 하면

위 : x = (1..sqrt(i.toFloat()).toInt()).filter { i % it == 0 }

아래 :  x.map { i / it }

 

나온 결과들을 이제 합쳐서 toSet() 하면 중복 사라지고 count()

 

여기까지 한 map을 println 해보면

 

 

위와 같은 결과가 나오고

 

다시 map으로 limit 보다 클 때는 power else it 

하고 sum 하면 결과 21

성공.