[프로그래머스 스위프트] 멀리 뛰기

아이디어

단순히 순열이나 조합을 구현하는 방법을 알면 자동으로 풀리지 않을까 생각했던 문제였다.

하지만 잘 생각해보니까 이 문제는 단순히 순열이나 조합으로 풀릴 문제가 아니다. 왜냐면 모든 경우의 수가 중요한 것이 아니라 오직 1과 2로 구성되어 있으므로 [1, 1, 2]이 있다면 여기서 서로 1의 위치가 서로 바뀌는 경우를 산정할 필요가 없기 때문이다.

결과적으로 이 문제는 피보나치수열이었다.. 즉 N = N - 1 + N - 2 인 것이다. 해결법이 안 보일 때는 노트에 손으로 쓰면서 법칙을 찾아내는 것이 중요하다는 생각이 들었다.

 

오답

테스트 케이스 7번부터 끝까지 "실패 (signal: illegal instruction (core dumped))가 발생한다. 인덱스 문제인가 하고 보니 그럴리는 없을듯하다. 그렇다면 정수가 너무 커졌을 가능성이 유력해 보였다. 하지만 문제에서 return을 Int로 명시해놓았으니 이것을 Int64로 수정하는 건 꺼림칙했다.

func solution(_ n:Int) -> Int {
    var result: [Int] = [0, 1, 2]
    if n < 3 {
        return result[n]
    }
    for i in 3...n {
        result.append(result[i - 1] + result[i - 2])
    }
    return (result.last!)%1234567
}

 

해답

약간 변칙적인 방법을 시도했다. 어차피 나는 배열 안에서 정답을 찾을 거고 문제에서 1234567로 나눈 나머지를 답으로 제출하라는 것은 이유가 있을 거라는 생각이었다. 오답 코드와 변경된 점은 정답 배열을 만들 때 문제에서 원하는 답인 1234567로 나눈 나머지로 배열에 넣는 것이다. 이렇게 하면 int값을 초과하지는 않을 거고 피보나치수열 특성상 되돌아가도 다시 그 경향이 유지될 거라 생각했다. 수학적으로 맞는지는 모르겠지만 직감으로 추측했다.

func solution(_ n:Int) -> Int {
    var result: [Int] = [0, 1, 2]
    if n < 3 {
        return result[n]
    }
    for i in 3...n {
        result.append((result[i - 1] + result[i - 2])%1234567)
    }
    return result.last!
}