[프로그래머스/자바] 피보나치 수

  

❌ 재귀 함수를 이용한 실패 답안 ❌

  

class Solution {
    public int solution(int n) {
        return fibonacci(n) % 1234567;
    }
    
    private int fibonacci(int n) {
        if(n == 0) return 0;
        if(n == 1) return 1;
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

  

실행하니 테스트 케이스 7번부터 시간 초과가 떴다.

n이 커지면서 int 범위를 넘어서는 값이 들어가기 때문인 것 같다.

 

---

✅ 통과된 답안 ✅

  

class Solution {
    public int solution(int n) {
        int a = 0;
        int b = 1;
        int sum = 0;

        for(int i=2; i<=n; i++) {
            sum = (a + b) % 1234567;
            a = b;
            b = sum;
        }

        return sum;
    }
}

 

n의 값은 2 이상이므로 n이 0이나 1일 때를 위한 if문은 사용하지 않았고, for문의 i 값은 2부터 시작된다.

실패 답안은 피보나치 수를 계산한 뒤 마지막으로 1234567을 나누었는데, for문을 돌면서 계산된 값을 그때그때 1234567로 나누는 방법으로 바꾸었다.