프로그래머스 - L2 피보나치 수

설계

n 만큼 배열을 생성해 2…n 범위를 순회하여, 피보나치 규칙에 맞게 배열을 채워나가는 방법!

git : 피보나치 수

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

---

문제 풀이

원하는 크기만큼 배열을 생성

0, 1번째 기본 0, 1 채워넣기

입력 받은 수 만큼 for 순회하여 생성 된 배열을 채워준다.

배열의 맨 마지막 수을 반환 값으로 출력

// n은 2 이상 100,000 이하의 자연수

func solution(_ n:Int) -> Int {
    var fibonacciArray = Array(repeating: 0, count: n + 1)
    fibonacciArray[0] = 0
    fibonacciArray[1] = 1
    
    for index in 2...n {
        fibonacciArray[index] = (fibonacciArray[index-1] + fibonacciArray[index-2]) % 1234567
    }
    
    guard let result = fibonacciArray.last else {
        return -1
    }
    
    return result
}

func getFibonacciNumber(index: Int) -> Int {
    if(index == 1) {
        return 1
    }
    if(index == 0) {
        return 0
    }
    
    return getFibonacciNumber(index: index - 2) + getFibonacciNumber(index: index - 1)
}

설계 방식대로 하면 시간복잡도 O(n) 것은 알고 있었는데 재귀방식으로 할 경우가 궁금하여, 재귀로도 진행했으나 시간초과였습니다.

재귀방식 일 경우 시간복잡도는 O(n^2) 입니다! 자세한건 시간복잡도 관련 글을 한번 포스팅해보도록 하겠습니다.

다른 사람 풀이 분석

프로그래머스 - fc750r , 김영욱

func solution(_ n:Int) -> Int {
    var v1: Int = 0
    var v2: Int = 1

    for _ in 2...n {
        let v = v1 + v2
        v1 = v2
        v2 = v % 1234567
    }

    return v2
}

메커니즘은 동일합니다!

사실 문제에 제시 된 1234567에 뭔가 함정이 있을거 같아 나머지에 대한 규칙을 찾았었는데… 찾지 못 하였습니다.

정리

심플 이스 베스트

---