[Swift] [11일차] 멀리뛰기

핀·2024년 12월 18일

SwiftAlgorithm

목록 보기

14/105

이전에 풀었던 +1 or -1 해서 결과값 만든느 방법 갯수 찾는거랑 엄청 비슷하게 느껴져서 비슷하게 풀이를 해봤다

func solution(_ n: Int) -> Int {
    var cnt = 0
    func jump(_ arrive: Int) {
        if arrive == n {
            cnt += 1
            return
        }
        else if arrive > n {
            return
        }
        jump(arrive + 1)
        jump(arrive + 2)
    }
    jump(0)
    return cnt
}

시간초과 실패

1234567로 니눈 나머지를 출력하라고 해서 나눠줬는데, 역시나 바로 풀리지는 않았고,
n이 1이상 2000이하라서 n을 건들건 또 딱히아닌데 어디서 줄일 수 있을지를 좀 고민하는데 시간을 쓴 것 같다.

피보나치 ?

노트에 좀 끄적여봤다. 어처피 1칸 or 2칸 이니까 이걸 차례대로 써보니까 피보나치 수열이랑 똑같다는 것을 알았다.

3칸까지 도착하기 위해서는 1칸 + 2칸점프 or 2칸 + 1칸점프니까
f(3) = f(1)+f(2)
그림으로 나타내면! 이렇게 되니까 f(3) 은 1+2 인 3이 나오게 된다 !

근데 fibo값을 저장을 해줘야할 것 같아서 다음과 같이 짰는데, 완전 실패로 나왔다.(시간 초과 안뜬건 호재일지도 ? )

아마 인덱스 관련 에러가 아닐까 싶은 ,, ?
(signal: illegal instruction (core dumped))

func solution(_ n: Int) -> Int {
    var fibo_array: [Int] = Array(repeating: 0, count: n + 1)
    fibo_array[0] = 1; fibo_array[1] = 1
    if n < 2 { return fibo_array[n] }
    for i in 2 ... n {
        fibo_array[i] = fibo_array[i-1] + fibo_array[i-2]
    }
    return fibo_array[n] % 1234567
}

코드는 엄청 간결해지긴했는데, 이제 인덱스 관련해서 에러를 잡아내야 했다.

값을 한번 크게 줘봤더니 다음과같은 에러가 떴다. index out of range가 아니라,

Swift runtime failure: arithmetic overflow 라는 에러였다.

n을 큰값을 주니까 92쯤에서 빠그라졌다.

큰 수를 계산하는 과정에서 타입으로 선언된 Int가 계산할 수 있는 최대치를 넘은것 같았다. 그래서 이게 값이 1234567를 안넘게끔 중간에 나눠주면서 해결하고자 했는데,
그래서 return에 있었던 %1234567을 위로 올려줬다. 과정에 있는 fibo_array[i]값을 전부 작게 유지할 수 있게 다듬었더니 이제 에러가 안떴고, 제출하니 정답처리가 될 수 있었다.

이제 에러가 안뜨는 모습

완성 코드

func solution(_ n: Int) -> Int {
    var fibo_array: [Int] = Array(repeating: 0, count: n + 1)
    fibo_array[0] = 1; fibo_array[1] = 1
    if n < 2 { return fibo_array[n] }
    for i in 2 ... n {
        fibo_array[i] = (fibo_array[i-1] + fibo_array[i-2]) % 1234567
    }
    return fibo_array[n]
}

타인의 코드

func solution(_ n:Int) -> Int64 {
    let DIV:Int64 = 1234567;
    var n0:Int64=0, n1:Int64=1;
    if(n<2) {return Int64(1);}
    var sum:Int64 = 0;
    for _ in 0..<n {
        sum = n0+n1;
        n0 = n1;
        n1 = sum % DIV;
    }
    return n1;
}