[프로그래머스_Kotlin] 멀리 뛰기

프로그래머스

 

문제

• 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는
• (1칸, 1칸, 1칸, 1칸)
• (1칸, 2칸, 1칸)
• (1칸, 1칸, 2칸)
• (2칸, 1칸, 1칸)
• (2칸, 2칸)
• 의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다.

 

 

제한 사항

• n은 1 이상, 2000 이하인 정수입니다.

 

 

입출력 예

 

 

 

내 풀이

전형적인 점화식이여서 간단히 풀었다.

class Solution {
    fun solution(n: Int): Long {
        var answer = longArrayOf(1,1)

        if (n == 1) return 1

        for (i in 1 until n) {
            answer[i+1] += (answer[i-1] + answer[i]) % 1234567
        }

        return answer[n-1]
    }
}

 

 

다른사람의 풀이

class SolutionAnother {
    fun solution(n: Int): Long = getFibonacci(n + 1)
    private tailrec fun getFibonacci(currentNumber : Int, acc : Long = 0, prevSum : Long = 1) : Long =
        if(currentNumber == 0) acc
        else getFibonacci(currentNumber - 1, prevSum, (prevSum + acc) % 1234567)
}

 

tailrec ?

먼저 꼬리 재귀(Tail Recursion)란?

어떤 함수가 직간접적으로 자기 자신을 호출하면서도 그 호출이 마지막 연산인 경우를 뜻한다.

이 마지막 연산인 호출을 '꼬리 호출'이라 한다.

일반적인 재귀 호출과는 다르게, 꼬리 재귀는 함수가 자신을 호출함과 동시에 종료된다.

재귀 호출이 반복되면서 깊이가 깊어지면 스택 오버플로우가 발생할 수 있는데, 꼬리 호출일 때는 스택 오버플로운가 발생하지 않는다.

왜?

컴파일러가 해당 문제를 일으키는 스택 프레임을 재사용하기 때문이다.

 

 

코틀린에서 tailrec 키워드를 사용해 꼬리 재귀 함수를 작성할 수 있다.

 

사용 조건

tailrec 키워드가 붙은 함수는 함수의 마지막 작업을 자기 자신을 호출하는 형태여야 한다.

 

예시)

팩토리얼 계산을 예로 들 수 있다.

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

 

tailrec fun factorial(n: Int, acc: Long = 1): Long {
    return if (n <= 1) {
        acc
    } else {
        factorial(n - 1, n * acc)
    }
}

n*acc의 결과를 다음 재귀 호출에 바로 전달해서 각 재귀 호출이 끝나는 즉시 스택 프레임을 제거할 수 있다.

 

현재의 스택 프레임을 재활용하고, 새로운 스택 프레임을 생성하지 않아도 된다.

-> 메모리 사용량을 크게 줄일 수 있고, 스택 오버플로를 방지할 수 있다.

 

 

ref

[Kotlin] tailrec(꼬리 재귀)란