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

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

프로그래머스

LV 2

 

구현 방법

피보나치 보자마자 재귀(Top-down)로 후딱 구현했는데 런타임 에러가 났다.  문제 범위가 "n은 2 이상 100,000 이하인 자연수입니다." 여서, 재귀로 풀 경우 중복되는 계산이 많아져서 비효율적이다. 

그래서 dp를 이용해서 반복(Bottm-up)으로 구현했다. 그런데도 오류가 떠서 찾아보니 자바 int 자료형의 경우, 

-2,147,483,648 ~ 2,147,483,647 사이의 범위를 가지고, 넘어가게 되면 값이 달라진다.

따라서 문제에서 "피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수"라는 조건을 준것이다.

위의 조건을 고려하여 구현하면 통과된다.

 

코드

class Solution {
    public int solution(int n) {
        int[] answer = new int[n + 1];
        
        answer[0] = 0;
        answer[1] = 1;
        for(int i = 2; i < n + 1; i++) {
            answer[i] = (answer[i -1] + answer[i - 2]) % 1234567;
        }
        
        return answer[n];
    }
}

 

느낀 점

문제에서 "피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수"라는 조건이 없는 경우는 범위가 더 넓은 long 타입으로 변경해서 구현하면 될거 같다. 

추가로 개발 과정에서 DB에서 튜플의 고유 식별 번호를 BigInt나 Long 타입으로 하는데, 데이터의 양이 많을 경우를 고려하기 위해서라는걸 새삼 다시 깨닮았다.

 

참고 블로그

https://inpa.tistory.com/entry/JAVA-%E2%98%95-%EA%B8%B0%EB%B3%B8-%EC%9E%90%EB%A3%8C%ED%98%95-%EC%A2%85%EB%A5%98-%EC%B4%9D%EC%A0%95%EB%A6%AC-int-double-char-String

☕ JAVA 데이터 타입 종류 총정리 (int / double / char / String / boolean)