[프로그래머스] 피보나치 수 (Java)

코딩테스트 연습 - 피보나치 수

 

작성 코드

- 처음에는 레벨 2에 이게 왜 있는지는 잘 이해가 되지 않았는데, 재귀로 풀어내니 시간초과가 떴다.

//시간초과 코드
class Solution {
    public int solution(int n) {
        int answer = 0;
        
        answer = fibonacci(n) % 1234567;
        
        return answer;
    }
    
    int fibonacci(int n){
        
        if(n == 0 || n == 1)
            return n;
        
        return fibonacci(n-1) + fibonacci(n-2);
    }
}

 

반복문으로 고쳤는데도 해결이 안 됐는데 알고보니 integer의 범위를 넘어가서 생기는 문제였음을 알게되었다.

(참고 : 7번부터 오답이 나오는 이유)

//범위문제로 7번 이후 통과못한 코드
class Solution {
    public int solution(int n) {
       
        int answer = 0;

        int[] array = new int[2];

        array[0] = 0;
        array[1] = 1;

        if(n == 0 || n == 1){
            answer = n;
        }else{
            
            for(int i=0; i<n-1; i++){
                array[i%2] = array[0] + array[1];
            } 
            
            answer = array[n%2] % 1234567;
        }

        return answer;
    }
    
}

 

먼저 1234567로 나눠주어 도출된 나머지값들로만 피보나치 수열을 만들면 해결된다. 나는 두 칸짜리 int 배열을 활용하여 좌우를 오가며 저장되게끔 만들었다.

//통과한 코드
class Solution {
    public int solution(int n) {
       
        int answer = 0;

        int[] array = new int[2];

        array[0] = 0;
        array[1] = 1;

        if(n == 0 || n == 1){
            answer = n;
        }else{
            
            for(int i=0; i<n-1; i++){
                array[i%2] = (array[0] + array[1]) % 1234567;
            } 
            
            answer = array[n%2];
        }

        return answer;
    }
}