[프로그래머스 코딩테스트 with JAVA] 피보나치 수

피보나치 수

Lv. 2 | 링크 https://school.programmers.co.kr/learn/courses/30/lessons/12945

피보나치 수는 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 이하인 자연수입니다.

입출력 예

입력 예시	출력 예시
3	2
5	5

 

입출력 예 설명

피보나치수는 0번째부터 0, 1, 1, 2, 3, 5, ... 와 같이 이어집니다.

 

소스코드 

import java.math.BigInteger;

class Solution {
    public int solution(int n) {
        long answer = 0L;
        long preOne = 1L;
        long preTwo = 1L;
        
        for(int i = 1; i<=n-2; i++){
            answer = (preOne + preTwo)%1234567;
            preOne = preTwo;
            preTwo = answer;
        }
        
        return (int)(answer);
    }
}

처음에는 배열로 작성했었는데 메모리 낭비가 심한 느낌이 들어 3개의 변수만 사용하는 방식으로 로직을 변경해보았다.
수의 범위가 커서 int로 처리하면 테스트 케이스에서 오류가 나기 쉽다. Java로 하는 경우 long과 나머지 처리를 함께하거나 BigInteger를 사용해야 할 것 같다. 피보나치 수열은 재귀함수로 해결할 수 있지만 메모이제이션 처리를 하지 않으면 동일한 매개변수의 메소드 호출이 반복될 수 있으니 주의해야한다. 자세한 내용은 아래 글을 참고하면 좋을 것 같다:)

[이것이 코딩 테스트다 with Java] 다이나믹 프로그래밍 (Dynamic Programming)

 

 

GitHub Link

GitHub - Leeyeonjae/coding-test: 코딩 테스트 연습