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

피보나치 수

문제 설명

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

입출력 예

n	return
3	2
5	5

입출력 예 설명

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

해결한 나의 코드

function solution(n){
	var answer = []
    for(var i=0; i<=n; i++){
      if(i==0) answer.push(0)
      if(i==1) answer.push(1)
      if(i>=2){
        var sum = answer[i-1] + answer[i-2]
      	answer.push(sum % 1234567)
      }
    }
  var result = answer[n]
  return result 
}

나의 알고리즘

1. for문으로 반복하여 피보나치 수열을 구한다.
2. 피보나치 수를 구할 때마다 % 1234567을 해준다.
3. n번째 피보나치 수를 리턴한다.

나뿐만 아니라 다른 사람들도 문제 설명의 부족함을 토로했다.

n번째 피보나치 수를 1234567로 나눈 나머지를 리턴하라는 말이 n번째 피보나치 수만을 뽑아 1234567로 나눈 나머지 값을 리턴하라는 말이 아니라 n개의 피보나치 수열을 구할 때마다 1234567로 나눈 나머지값을 구한 값 중 n번째 수를 반환 하라는 말이었다. ㅎㅎ;

따라서 다음과 같은 시행착오를 거쳤다.

시간 초과 || 실패 코드

// 시간 초과
function solution(n){
	var answer = fibonacci(n) % 1234567
    return answer
}

function fibonacci(n){
	if(n == 0) { return 0 }
    else if(n == 1) { return 1 }
    else { return fibonacci(n-1) + fibonacci(n-2) }
    
}

우선 이 코드는 시간초과 && 실패한 코드이다.
피보나치 수를 구해야 하길래 (넘나 무의식적으로) 재귀 함수를 사용해야 한다고 생각했다.
안그래도 재귀 진짜 약한데.. 완전 재귀랄인데.. 연습도 할 겸 재귀를 사용했더니 웬걸 시간초과 떠버림.. 글구 어차피 매번 % 1234567 안해줘서 실패하기도 했다.

// 실패
function solution(n){
	var answer = []
    for(var i=0; i<=n; i++){
      if(i==0) answer.push(0)
      if(i==1) answer.push(1)
      if(i>=2){
        var sum = answer[i-1] + answer[i-2]
      	answer.push(sum)
      }
    }
  var result = answer[n] % 1234567
  return result 

그렇다. n번째의 피보나치 수만을 % 1234567 해주어서 실패 떴다.

질문하기 게시판을 보지 않았으면 꽤나 오랜 시간동안 힘들었을 문제였던 것 같다.