프로그래머스 코딩테스트 연습 Level 2 - 피보나치 수 (JavaScript)

프로그래머스 코딩테스트 연습 Level 2 - 피보나치 수 (JavaScript)

 

Programmers(프로그래머스)의 코딩테스트 연습문제 Level 2 중,

[피보나치 수] 문제를 JavaScript를 사용하여 해결해 보도록 하겠습니다.

 

문제

문제 설명

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

 

입출력 예

n	return
3	2
5	5

 

입출력 예 설명

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

 

 

작성한 답

solution.js

처음 작성한 답

function solution(n) {
    let arr = Array.from({length: n + 1});
    arr[0] = 0;
    arr[1] = 1;
    for(let i = 2 ; i < arr.length ; i++) {
        arr[i] = (arr[i - 1] + arr[i - 2]) % 1234567;
    }
    return arr.pop();
}

 

개선한 두번째로 작성한 답

function solution(n) {
    let answer, t1 = 0, t2 = 1;
    for(let i = 2 ; i <= n ; i++) {
        answer = t1 + t2 % 1234567;
        t1 = t2;
        t2 = answer;
    }
    return answer % 1234567;
}

 

설명

이 문제는 크게 어려운 점이 없이 설명만 잘 읽어도 문제없이 해결할 수 있는 문제였지만,

방식에서 여러가지 차이가 있었습니다.

 

위의 두가지 방법으로 구현하기 전, 재귀적으로 함수를 호출하는 방법으로 구현하였으나 시간때문에 실패하였고,

위 두가지 방법은 모두 성공하였으나,

처음 작성한 방법인 배열을 만들어 담는 방식으로 먼저 구현을 하였더니 굳이 배열을 사용할 필요 없이

배열을 사용한 방법에서 반복문을 돌면서 현재 index에 들어갈 바로 앞 전의 값과 2단계 앞의 값만 얻어올 수 있기만 하면 된다는 점을 파악하여 굳이 배열을 사용할 필요가 없다고 판단해,

number형을 담을 임시 변수만 2개 만들어 사용하는 방법으로 구현하였습니다.

 

반복문 안에서도 answer에 1234567의 나머지 값을 넣어주는 이유는 테스트 과정에서 너무 큰 수를 담게 되었을 때 범위를 초과하기 때문이고, 이 같은 방식을 사용해도 정답을 구하는데 이상이 없습니다.

 

 

 

도움이 되셨다면 공감, 댓글 부탁드립니다!

궁금하신 점이나 요청사항은 언제든지 말씀해주세요!

피드백도 언제나 환영입니다!

 

감사합니다.