[프로그래머스][Lv.2][JAVA]피보나치 수

 

문제

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

 

 

---

 

분석

1. F(0)이 될 때까지 재귀함수로 계속 값을 더해줘야 함. 
   => 성능 문제로 다른 방법을 택했다. 피드백과 답안 참고.
2. ' 2 이상의 n이 입력되었을 때, n번째 피보나치 수'는 쉽게 말하면 F(n)의 값이 되고, 그 수를 1234567로 나눈 나머지를 결과로 return.

 

---

 

피드백

1. 처음엔 간단하게 풀리나 했는데 제출 후 채점해보니 테스트1부터 14까지 케이스 중 7부터 14까지는 시간초과로 실패해버렸다. 제출했던 코드는 하기 참고. 어디서 문제였을지 찬찬히 다시보는데 일단 1234567로 나눈 나머지값이라는 부분을 생략했음을 깨달았다. 일단 나머지값 구하는 부분부터 추가.
2. 아마 피보나치수를 단순히 재귀함수로 구하는 게 아니라 더 효율적인 방법을 찾아야 하는 듯. 피보나치가 계속 그 이전의 수, 이전의 이전의 수... 이렇게 이어지니까 차라리 그 수를 계속 이전 수를 찾아 더해오는 것이 아니라 배열에 담아둔다면 어떨까? n-1 번 피보나치를 구하면 배열이 완성될 것이고, 그 배열을 통해 n-2 번 피보나치는 배열에서 n번 배열의 요소를 찾아 더하면 별도로 재귀를 통하지 않더라도 가능할 것으로 보인다. 즉, 0번부터 n-1번까지의 피보나치 배열을 int[] 로 완성하면 수를 보다 쉽게 구할 수 있지 않느냐, 하는 생각. 
   그래서 코드를 고쳐봤는데, 이번엔 실패한 테스트는 다른데 시간초과가 아니라 그냥 실패가 떴다. 코드는 역시 하기 참고. 경험상 이렇게 숫자가 점점 엄청나게 커지는 경우에는 int 객체 범위를 벗어나서 실패하는 경우가 많았다. 처음부터 고려했다면 좋았겠지만 어쨌든 지금 생각이 났으니 이 부분을 고쳐봤다. 챗지의 도움을 받아 해당 부분 수정을 거쳤고, 결과는 통과. 
   최종적인 코드는 답안 부분 참고. 

1. 첫 번째 제출 코드 

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

 

 

2. 두 번째 제출 코드

 

class Solution {
    public int solution(int n) {
    	// 피보나치 수의 배열
    	int[] fiboArr = new int[n+1];
    	
    	// 기본값
    	fiboArr[0] = 0;
    	fiboArr[1] = 1;
    	
    	// 나머지 배열 완성
    	for(int i = 2; i <= n; i++) {
    		fiboArr[i] = fiboArr[i-1] + fiboArr[i-2];
    	}
        return fiboArr[n] % 1234567;
    }
}

 

 

 

 

---

 

답안

class Solution {
    public int solution(int n) {
    	// 피보나치 수의 배열
    	int[] fiboArr = new int[n+1];
    	
    	// 기본값
    	fiboArr[0] = 0;
    	fiboArr[1] = 1;
    	
    	// 나머지 배열 완성
    	for(int i = 2; i <= n; i++) {
            fiboArr[i] = (fiboArr[i - 1] + fiboArr[i - 2]) % 1234567;
    	}
        return fiboArr[n];
    }
}

 

 

 

 

 

 

 

---

 

🔗링크

프로그래머스