[Algorithm] 프로그래머스 - 팩토리얼 (Kotlin)

i 팩토리얼(i!)은 1부터 i까지 정수의 곱을 의미한다. 5! = 5 * 4 * 3 * 2 * 1이다
정수 n이 주어질 때 조건을 만족하는 가장 큰 정수 i를 리턴하는 solution()을 완성하라

 

 

처음 풀 때에는 손도 대지 못해서 포기했던 문제인데 제한사항과 입출력 예를 보니 그제서야 어떻게 하면 좋을지 떠올랐다. 아쉽지만 이미 다른 사람의 풀이를 봤으니 어쩔 수 없다.

 

class Solution {
    fun solution(n: Int): Int {
        var answer = 0
        for (i in 10 downTo 1) {
            if (factorial(i) <= n) {
                answer = i
                break
            }
        }
        return answer
    }

    private fun factorial(n: Int): Int {
        return if (n == 1) 1
        else n * factorial(n - 1)
    }
}

 

다른 풀이를 확인한 결과 위의 코드를 더 짧게 작성한다면 아래와 같이 쓸 수 있다.

 

class Solution {
    fun solution(n: Int) = (2..n).find { n < factorial(it) }?.dec() ?: n

    private tailrec fun factorial(n: Int, run: Int = 1): Int = if (n == 1) run else factorial(n - 1, run * n)
}

 

tailrec 키워드는 꼬리재귀(tail recursive)란 뜻으로, 추가 연산 없이 자기 스스로 재귀적으로 호출하다가 어떤 값을 리턴하고 끝나는 함수를 말한다. 이걸 써서 좋은 점은 재귀함수가 호출되면서 소비되는 스택을 아낄 수 있다는데 와닿지는 않는다. 아래는 참고한 블로그다.

 

https://codechacha.com/ko/kotlin-tailrect/

Kotlin - tailrec(꼬리재귀)에 대해서 알아보기

 

그리고 dec()의 설명과 원형은 아래와 같다.

 

https://kotlinlang.org/api/latest/jvm/stdlib/kotlin/-int/dec.html

dec - Kotlin Programming Language

1씩 감소한 값을 반환한다

public operator fun dec(): Int

 

설명만 써놓기는 애매했는지 공식 홈페이지에 예제 스니펫이 있다.

 

val a = 3
val b = a.dec()
println(a) // 3
println(b) // 2

var x = 3
val y = x--
    println(x) // 2
println(y) // 3

val z = --x
println(x) // 1
println(z) // 1