[Lv.2] 피보나치 수 : Java

프로그래머스

 

 

 

이해하기

피보나치 수? 분명 풀어봤었는데? 하고 만만히 봤다가 꽤나 오래 걸렸던 문제ㅠ

 

첫번째 아이디어는 재귀로 풀이하기였다.

class Solution {
    public int solution(int n) {
        int answer = fibonacci(n) % 1234567;

        return answer;
    }

    public int fibonacci(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }

        return fibonacci(n - 2) + fibonacci(n - 1);
    }
}

 

테스트 케이스는 잘 돌아가길래 통과할 줄 알았는데 7번부터 줄줄이 시간 초과...

그러고보니 피보나치 수 문제를 풀 때 재귀를 사용하면 매번 계산해야해서 시간이 오래 걸린다고 들었던 기억이 났다.

 

그래서 생각한 두번째 아이디어는 이전 계산값을 list에 저장하고 바로바로 불러오기였다.

import java.util.*;

class Solution {
    List<Integer> list = new ArrayList<>();

    public int solution(int n) {
        int answer = 0;

        list.add(0);
        list.add(1);
        list.add(1);

        if (n == 0) {
            return 0;
        } else if (n == 1 || n == 2) {
            return 1;
        } else {
            fibonacci(n);
            answer = list.get(n);
        }

        return answer % 1234567;
    }

    public void fibonacci(int n) {
        int idx = list.size() - 1;
        while (idx != n) {
            list.add(list.get(idx - 1) + list.get(idx));
            idx++;
        }
    }
}

 

이 코드 또한 6번까지는 잘~ 통과되다가 7번부터 실패, 실패, 실패...

아까는 풀이는 제대로였지만 시간초과가 문제였다면, 지금건 계산 로직에서 실패가 뜬 것 같다고 추정했다.

 

결국 다른 분의 글을 참고한 후 다시 풀었다...

 

 

문제풀이

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

참고했던 블로그 글!

미리 계산해서 저장해둔 후 불러온다는 아이디어는 비슷했지만 배열을 사용하셨다는 점과 1234567로 나머지 계산을 미리 한 후 저장하셨던 점이 차이점인 것 같다.

아마 두번째 풀이에서 실패가 떴던 게 나머지 연산을 미리 해주지 않아서일 것 같다는 생각이 든다.

 

class Solution {
    public int solution(int n) {
        int answer = fibonacci(n);
        return answer;
    }

    public int fibonacci(int n) {
        int[] fibo = new int[n + 1];
        fibo[0] = 0;
        fibo[1] = 1;

        for (int i = 2; i <= n; i++) {
            fibo[i] = (fibo[i - 2] + fibo[i - 1]) % 1234567;
        }

        return fibo[n];
    }
}

 

그치만 분명 재귀 파트 문제였는데 이런 풀이는 재귀 형식이 아니지 않나 싶었다ㅜ