프로그래머스 Lv. 2 Swift 알고리즘 - 멀리 뛰기

못참고 답을 확인한 문제이다...

논리적으로는 간단한 문제인데... 왜 이리 시간초과가 나던지 ㅠㅠ

 

1칸 혹은 2칸 두가지 경우를 가지고 n칸 만큼 움직이는 경우의 수를 구하는 문제이다.

결국 1과 2라는 원소를 가지고 Combination 개념을 적용시키면 풀 수 있다.
라고 생각했다. 그래서 계속 Combination 개념하에 코드를 짜고 풀었다... 하지만 도저히 시간이 맞춰지지가 않았다.

 

그래서 찾아보니 이게 피보나치 수열을 따르더라..! Combination에 눈이 돌아가서 더 쉬운 규칙이 존재한다는 것을 깨닫지 못했다!

이런 경우가 가장 가슴 아픈 경우...

 

 

 

이 문제를 풀면서 생각한 논리적 흐름

1. 1, 2, 3 순차적으로 가능한 경우의 수를 따져보면 그 수가 피보나치 수열을 따른 다는 것을 알 수 있다.
2. 1칸: 1, 2칸: 2, 3칸: 3, 4칸: 5, 5칸: 8...
3. 그래서 1과 2는 1, 2를 고정적으로 넣어두고 3칸부터 그 전전칸 + 전칸 값을 더해주면 된다.
4. 1234567로 나눈 나머지를 사용하는 것은 아래 링크에 이유가 있다.

(왜 1234567로 나눈 나머지 값을 사용할까? : https://school.programmers.co.kr/questions/11991?question=11991)

 

 

* 처음 코드

import Foundation

func solution(_ n:Int) -> Int {
    var ans = 0
    var array1: [Int] = []
    let number = Int(floor(Double(n)/Double(2)))

    for i in 0...number {
        array1.append(n-(2*i))
    }

    for i in 0...array1.count-1 {
        ans += combination(i+array1[i], i)
    }

    return ans
}

func combination(_ total: Int, _ shouldSelect: Int) -> Int {
    if total == shouldSelect || shouldSelect == 0 {
        return 1
    } else {
        return combination(total-1, shouldSelect) + combination(total-1, shouldSelect-1)
    }
}

처음 코드의 경우 n개의 칸에서 나올 수 있는 경우와 원수의 개수를 array에 정의하고, 그 원소들을 이용하여 3C1, 4C2 등의 Combination 결과값을 이용하고자 했다. 하지만 이런 방법은 값은 나오지만 결국 꽤나 많은 테스트 케이스에서 시간을 초과해버려 쓸 수 없었다. 이때 또 배운 것이 Swift에는 순열과 조합이 없다는 것이었다. 찾아보니 Python이라던가 등등은 기본 라이브러리에 순열 조합과 같은 수학적 알고리즘이 내포되어 있는데 Swift는 개발자가 직접 만들어야 했다. 그래서 Combination 함수를 만드는데도 꽤 많은 시간을 썼다...

 

 

* 고친 코드

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

 

 

정리(Today I Learned)

1. 알고리즘은 확실히 수학문제이다..! 푸는 방법에 따라 정말 천차만별의 풀이법이 존재한다. 그 중 가장 간단하고 비용이 적은 방법을 잘 골라내는 것이 알고리즘 고수!