🔥TIL🔥스파르타 | 약수 구하는 알고리즘

약수 구하는 알고리즘

문제링크

정수 N이 입력됐을 때 N의 소수를 구하는 알고리즘을 짜보자.

약수란?

어떤 수를 나누어 떨어지게 하는 수
ex) 12의 약수는? 1,2,3,4,6,12

어떻게 풀어야 할지 생각해 보자

1. 12의 제곱근인 3까지, 0으로 나누어 떨어지는 수를 구해보자
   12 % 1 = 0
   12 % 2 = 0
   12 % 3 = 0
2. 1,2,3이 구해졌다
3. 이렇게 구해진 숫자들로 다시 12를 나누자
   12 / 1 = 12
   12 / 2 = 6
   12 / 3 = 4
4. 12,6,4가 구해졌다
5. 1,2,3,4,6,12가 나왔다.

풀이 코드

import kotlin.math.sqrt

class Solution {
    fun solution(n: Int): Int { 
        
        val N = (sqrt(n.toDouble())).toInt()
        val answerList = mutableListOf<Int>()
        
        for (i in 1..N){
            if(n % i == 0){
                answerList.add(i)
            }
        }
        
        for (i in 0..answerList.size-1){
            if(n % answerList[i] == 0){
                answerList.add(n / answerList[i])
            }
        }
        
        return answerList.distinct().sum()
    }
}

사용한 개념들

1. 제곱근을 구하기 위해 사용한 math 라이브러리에 정의된 sqrt함수

import kotlin.math.sqrt //import 해줘야 한다.

print(sqrt(4.0)) 		//Double이나 Float 자료형이 들어가야 한다.

>> 2.0

2. 수정가능한 리스트인 mutable list
   Collection에는 List, Map, Set이 있다.
   또한 Mutable과 immutable으로 구분된다.

코틀린의 List는 기본적으로 immutable 이다.
immutable : 불변의

val list: List<Int> = List(3,  {i -> i})
val list: List<Int> = listOf(0, 1, 2)

위처럼 선언된 리스트들은 수정이 불가능하다.

하지만 mutable로 선언할 경우 값을 변경할 수 있다.

val answerList = mutableListOf<Int>()
answerList.add(3)
print(answerList)

>> 3

3. 리스트에서 중복요소 제거

answerList.distinct()

더 생각해 봐야 할 것

다른 사람의 풀이를 봤는데

answer = (1..n).filter { n % it == 0 }.sum()

이런 형식으로 풀어놨다.
내가 푼 방식은 시간 복잡도가 O(√N)이 되므로, 10억의 입력이 들어온다해도, 약 3만번의 연산으로 약수를 구할 수 있다.
근데 위의 풀이대로 풀면 n까지 하나하나 0으로 나눠지는지 검사해서 시간 복잡도가 O(N)이지 않을까??

😮더 공부해야 할 것

Collection에 대해 더 공부해 보자
참고 자료 : https://soopeach.tistory.com/62