[프로그래머스] 피보나치 수 Kotlin

안녕하세요. 이번에는 프로그래머스 피보나치 수 문제를 풀어보려고 합니다.

 

https://school.programmers.co.kr/learn/courses/30/lessons/12945

프로그래머스

---

Problem

피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2)가 적용되는 수입니다.

예를 들어

F(2) = F(0) + F(1) = 0 + 1 = 1
F(3) = F(1) + F(2) = 1 + 1 = 2
F(4) = F(2) + F(3) = 1 + 2 = 3
F(5) = F(3) + F(4) = 2 + 3 = 5
와 같이 이어집니다.

2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.

 

[제한 사항]

○ n은 2 이상 100,000 이하인 자연수입니다.

사진 1. 입출력 예

---

Solution

class Solution {
    fun solution(n: Int): Int {
        var answer = 0
        var dp = IntArray(n + 1) 

        dp[0] = 0
        dp[1] = 1

        for(i in 2..n) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % 1234567    
        }

        return dp[n]
    }
}

 이번 문제는 백준을 풀 때 봤던 피보나치 수 문제랑 비슷해서 dp를 활용해서 문제를 풀어보았습니다. 

 

https://echung93.tistory.com/50

[백준] CLASS3 1003 피보나치 함수 - JAVA [자바]

 백준의 풀이가 궁금하시면 위에 링크를 보고 오시면 됩니다.

 

1. 다른 사람 코드

class Solution {
    fun solution(n: Int): Int {
        val answer = fibo(0, 1, 1, n)
        return answer
    }

    tailrec fun fibo(a: Int, b: Int, m: Int, n: Int): Int {
        if (m <= n) {
            return fibo(b, (a + b) % 1234567, m + 1, n)
        } else {
            return a
        }
    }
}

  저의 코드와 다르게 피보나치 수를 Kotlin에서 제공해 주는 tailrec으로 푼 문제가 있어서 가져와봤습니다. tailrec은 꼬리재귀 함수로 코틀린에서 컴파일러가 해당 함수를 반복문으로 최적화할 수 있는 장점이 있는 함수입니다. 

---

Performance

1. 내가 작성한 코드	2. 다른 사람 코드