Kotlin/Exercise

완벽한 숫자 - 자연수에대한

봄석 2019. 3. 27. 00:20

완벽한 숫자 - 자연수에대한

Nicomachus (60 - 120 CE) 분류 체계에 따라 번호가 완전하고 풍부하며 결핍되었는지 확인하십시오.


그리스 수학자 인 니코 마 쿠스 (Nicomachus) 는 자연수에 대한 분류 체계를 고안하여 각자가 분량의 합계 에 기초하여 완벽 하고 풍부 하거나 부족한 범주에 속하는 것으로 나타 냈습니다 . 분량 합은 수 자체를 포함하지 않는 수의 합계로 정의됩니다. 예를 들어, 15의 분량 합은 (1 + 3 + 5) = 9

  • 완벽 : 분량 합 = 번호

    • 6은 (1 + 2 + 3) = 6이므로 완벽한 수입니다.
    • 28은 (1 + 2 + 4 + 7 + 14) = 28이므로 완벽한 수입니다.

  • 풍부 : 분랑 합> 수

    • 12는 (1 + 2 + 3 + 4 + 6) = 16이기 때문에 풍부한 수입니다.
    • 24는 (1 + 2 + 3 + 4 + 6 + 8 + 12) = 36이기 때문에 풍부한 수이다.
  • 불완전 : 분량 합 <수
    • 8은 (1 + 2 + 4) = 7이므로 불완전한 수입니다.
    • 소수는 부족하다.

주어진 숫자가 완벽한 지 판단하는 방법을 구현하십시오 .


TestCode

class NaturalNumberTest {
 
 
    enum class Classification {
        DEFICIENT, PERFECT, ABUNDANT
    }
 
    @Test
    fun smallPerfectNumberIsClassifiedCorrectly() {
        assertEquals(Classification.PERFECT, classify(6))
    }
 
    @Test
    fun mediumPerfectNumberIsClassifiedCorrectly() {
        assertEquals(Classification.PERFECT, classify(28))
    }
 
    @Test
    fun largePerfectNumberIsClassifiedCorrectly() {
        assertEquals(Classification.PERFECT, classify(33550336))
    }
 
    @Test
    fun smallAbundantNumberIsClassifiedCorrectly() {
        assertEquals(Classification.ABUNDANT, classify(12))
    }
 
    @Test
    fun mediumAbundantNumberIsClassifiedCorrectly() {
        assertEquals(Classification.ABUNDANT, classify(30))
    }
 
    @Test
    fun largeAbundantNumberIsClassifiedCorrectly() {
        assertEquals(Classification.ABUNDANT, classify(33550335))
    }
 
    @Test
    fun smallestPrimeDeficientNumberIsClassifiedCorrectly() {
        assertEquals(Classification.DEFICIENT, classify(2))
    }
 
    @Test
    fun smallestNonPrimeDeficientNumberIsClassifiedCorrectly() {
        assertEquals(Classification.DEFICIENT, classify(4))
    }
 
    @Test
    fun mediumNumberIsClassifiedCorrectly() {
        assertEquals(Classification.DEFICIENT, classify(32))
    }
 
    @Test
    fun largeDeficientNumberIsClassifiedCorrectly() {
        assertEquals(Classification.DEFICIENT, classify(33550337))
    }
 
    @Test
    fun edgeCaseWithNoFactorsOtherThanItselfIsClassifiedCorrectly() {
        assertEquals(Classification.DEFICIENT, classify(1))
    }
 
    @Test(expected = RuntimeException::class)
    fun zeroIsNotANaturalNumber() {
        classify(0)
    }
 
    @Test(expected = RuntimeException::class)
    fun negativeNumberIsNotANaturalNumber() {
        classify(-1)
    }
 

}


완벽한 숫자인지 판별하는 기준은, 자기자신을 제외한 모든약수를 더하는 것입니다 .


해결에 들어가기전에 약수에 대하여 알아보도록 하겠습니다 .

약수(約數, divisor)는 어떤 수를 나누었을 때 나머지가 0인 수를 말하며, 배수 관계와 서로 반대되는 개념이다. 약수는 보통 정수에 대해 정의되지만, 일반화하여 정역에 대해 정의하기도 한다.

출처: https://mygumi.tistory.com/122 [마이구미의 HelloWorld]



해결안 1) 1부터 자기자신까지 모든 수를 나누어서 나머지가 0인지 확인하기

fun classify(naturalNumber: Int): Classification {
        require(naturalNumber > 0)
        val divisors = mutableListOf<Int>().apply {
            for (a in 1..naturalNumber) {
                if (naturalNumber % a == 0)
                    this.add(a)
            }
        }
 
        return when {
            (divisors.sum() - naturalNumber) == naturalNumber -> Classification.PERFECT
            (divisors.sum() - naturalNumber) >= naturalNumber -> Classification.ABUNDANT
            else -> Classification.DEFICIENT
        }
    }



1) 1..naturalNumber를 for문을 이용하여 나누어서 , 나머지가 0이라면 divisors List에 추가합니다 

2) 모두 더한값(divisors의합) -naturalNumber가 자기자신(naturalNumber)와 같다면 PERPECT, 

더크다면 ABUNDANT, 적다면 ,DEFICIENT를 리턴합니다 .


해결안 2) compareTo,확장변수 ,fold 사용하기 

 private fun classify(naturalNumber: Int) = naturalNumber
        .apply { require(naturalNumber > 0) }
        .compareTo(naturalNumber.factors.sum())
        .let {
            when {
                it < 0 -> Classification.ABUNDANT
                it == 0 -> Classification.PERFECT
                else -> Classification.DEFICIENT
            }
        }
 
    private val Int.factors: List<Int>

        get() = (1..this / 2).fold(emptyList()) { factors, i -> if (this % i == 0) factors.plus(i) else factors }


1) naturalNumber가 먼저 0보다 큰지 확인합니다 (require)

2) compareTo 함수를 이용하여, 확장변수 Int.factors.sum()이 naturalNumber와 같은지, 다른지 적은지를 비교합니다 . 같다면 0, 크다면 1을 리턴합니다 

3) 확장변수 factors는 List<Int>형이며 ,  커스텀 getter를 통해 값을얻습니다 .

4) 1부터 자기자신/2 동안 fold함수를 호출합니다 .

5) fold함수는 fold(리턴값){리턴값,계산변수}입니다 .i는 1..this/2까지 증가하며, 

만약 들어온값 this를 i로 나눴을떄 값이 0이라면 ,리스트에 i를 더하고 그리스트를 리턴합니다 .

만약 들어온값 this를 i로 나눴을때 값이 0이아니라면, 리스트를 그대로 리턴합니다 .

6)리스트값을 모두더해 0인지, 더큰지, 적은지를 비교합니다 .



확장함수, 확장변수

- fun 확장하려는대상.함수명(또는변수명):Unit{}

-fun 확장하려는대상.함수명(또는변수명):리턴값 { return ..}

compareTo

공
JS
원주민
abstract operator fun compareTo(other: T): Int

이 객체와 지정된 객체를 비교합니다. 이 객체가 지정된 같으면 0을 리턴 , 음수는 그 이하라면 -1, 또는 양의 수는 그 이상이라면 1리턴


String.fold(initial:R){R,T->R} 함수

fold 함수의 원형

inline fun <T, R> Sequence<T>.fold(
    initial: R, 
    operation: (acc: R, T) -> R
): R

적산 값으로 시작 초기 값 및인가 동작을 전류 누산기 값 및 각 소자에 왼쪽에서 오른쪽으로한다. 

즉 누산기 같은 역할입니다. RxJava의 reduce와 비슷합니다 . 값을 계속 더해줄수 있습니다 .

fold는 겹이라는 뜻입니다.


List.plus()

원래 콜렉션의 모든 요소를 ​​포함하고 주어진 요소를 포함하는리스트를 리턴합니다 .

operator fun <T> Iterable<T>.plus(element: T): List<T>
operator fun <T> Collection<T>.plus(element: T): List<T>