02/06 알고리즘 공부(33) - 약수의 개수와 덧셈

조건

두 정수 left와 right가 매개변수로 주어집니다. left부터 right까지의 모든 수들 중에서, 약수의 개수가 짝수인 수는 더하고, 약수의 개수가 홀수인 수는 뺀 수를 return 하도록 solution 함수를 완성해주세요. (1 ≤ left ≤ right ≤ 1,000)

알고리즘 예상

1. 약수의 개수는 제곱수를 제외하면 모두 짝수개이다.
2. 따라서 제곱근을 구하는 알고리즘을 이용해 정수 제곱근이 있다면 더하고 없다면 뺀다.

 

초기 코드

class Solution {
    fun solution(left: Int, right: Int): Int {
        var answer: Int = 0
        return answer
    }
}

 

내 코드

import kotlin.math.sqrt

class Solution {
    fun solution(left: Int, right: Int): Int {
        var answer: Int = 0
        for(i in left..right){
            if(sqrt(i.toDouble())-sqrt(i.toDouble()).toInt().toDouble() == 0.0 ) answer -= i
            else answer += i
        }
        return answer
    }
}

 

다른 사람의 풀이

class Solution {
    fun solution(left: Int, right: Int): Int {
        return (left..right).map { i -> if ((1..i).filter { i % it == 0 }.size % 2 == 0) i else -i }.sum()
    }
}

class Solution {
    fun solution(left: Int, right: Int): Int {
        var answer: Int = 0

        for(i in left .. right) {
            var count = 0

            for(j in 1 .. i) {
                if(i % j == 0) count++
            }
            if(count % 2 == 0) answer += i
            else answer -= i

        }

        return answer
    }
}

class Solution {
    fun solution(left: Int, right: Int): Int = (left..right).fold(0){sum,idx -> sum + (idx * if(kotlin.math.sqrt(idx.toDouble()) % 1 == 0.toDouble()) -1 else 1) }
}

개선점 또는 배운점

1. 코드 박스를 없엔 코드가 꽤 있었다.
2. 제곱근을 toInt().toDouble()로 소숫점을 없에는게 아닌 %1.0을 통해 소숫점이 있는 지 확인하는 방법이 있었다.
3. map과 filter를 이용해 부호가 포함된 배열을 만들고 sum을 이용해 합을 구하는 방법을 배웠다.

 

개선된 코드

import kotlin.math.sqrt

class Solution {
    fun solution(left: Int, right: Int) = (left..right).fold(0){s,n -> s + (n * if(sqrt(n.toDouble()) % 1.0 == 0.0) -1 else 1)}
}