스위프트 코딩테스트 강좌, 계단 수 구하기

안녕하세요, 여러분! 오늘은 코딩테스트에서 자주 등장하는 문제 중 하나인 ‘계단 수 구하기‘ 문제를 다뤄보겠습니다. 이 글에서는 계단 수 문제의 정의, 해결 방법, 그리고 스위프트 코드 예제를 단계별로 살펴보겠습니다. 최종적으로는 효율적이고 간결한 코드 구현 방법과 다양한 테스트 케이스를 포함할 것입니다.

문제 정의

계단 수(n)는 길이가 n인 수로서, 연속된 두 자리의 차이가 1인 수를 의미합니다. 예를 들어, 123, 234, 321은 계단 수입니다. 하지만 122, 3456은 계단 수가 아닙니다. 여러분의 작업은 주어진 n에 대해 n자리 계단 수의 개수를 계산하는 것입니다.

문제의 예

1부터 9까지의 숫자를 사용하여 주어진 자리 수(n)의 계단 수를 구하는 문제를 예로 들어보겠습니다. 다음은 몇 가지 예시입니다:

n = 1: 결과 = 9 (1, 2, 3, 4, 5, 6, 7, 8, 9)
n = 2: 결과 = 17 (10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 90)
n = 3: 결과 = 32 (101, 121, 123, 210, 212, …)

문제를 해결하기 위한 접근법

이 문제를 해결하기 위해서는 동적 프로그래밍(Dynamic Programming) 기법을 사용할 수 있습니다. 계단 수의 성질에 따라서 한 자리 수의 경우와 그 위의 자리 수의 관계를 이용하여 문제를 푸는 방식입니다.

다이나믹 프로그래밍 접근법

우리는 먼저 계단 수의 길이를 n으로 하고, 가능한 수의 배열을 저장할 dp 배열을 설정합니다. dp[i][j]는 길이 i인 계단 수의 마지막 자리가 j일 때의 수의 개수를 의미합니다. 이 구성을 통해 점화식을 설정할 수 있습니다:

        dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

여기서 j는 0부터 9까지의 숫자를 가집니다. 즉, 마지막 자리가 0이라면, 이전 자리의 마지막 자리는 1밖에 올 수 없고, 마지막 자리가 9라면, 이전 자리의 마지막 자리는 8밖에 올 수 없습니다. 중간 값들은 양방향 모두 가능하다는 점을 유의해야 합니다.

기초 설정

이제 문제 해결을 위한 DP 테이블을 초기화하겠습니다. 계단 수의 경우 첫 자리 수는 1부터 9까지의 숫자이기 때문에:

    for j in 0...9 {
        dp[1][j] = 1
    }

이제 두 번째 자리부터 n자리까지의 반목문을 설정하여 dp 배열을 채워넣겠습니다.

스위프트 코드 구현

이제 위에서 설명한 내용을 바탕으로 스위프트로 코드를 구현해 보겠습니다.

    func countStairNumbers(n: Int) -> Int {
        // 각 자리수 별 계단 수의 갯수를 저장할 배열
        var dp = Array(repeating: Array(repeating: 0, count: 10), count: n + 1)

        // 1자리 수는 1~9까지 각각 1개의 경우
        for j in 1...9 {
            dp[1][j] = 1
        }

        // DP 배열 채우기
        for i in 2...n {
            for j in 0...9 {
                if j > 0 {
                    dp[i][j] += dp[i - 1][j - 1]
                }
                if j < 9 {
                    dp[i][j] += dp[i - 1][j + 1]
                }
            }
        }

        var totalCount = 0
        // n자리 수의 경우를 모두 더함
        for j in 0...9 {
            totalCount += dp[n][j]
        }

        return totalCount
    }

    // 사용 예
    let result = countStairNumbers(n: 3)
    print("3자리 수의 계단 수의 개수: \(result)") // Output: 32

코드 설명

위 코드는 주어진 n에 대해 n자리 계단 수의 개수를 반환합니다. 함수에서 dp 배열을 설정하고, 각 자리 수에 대해 가능성을 더해가며 각각의 경우를 계산합니다. 최종적으로는 n자리 수의 모든 경우의 수를 반환합니다.

테스트 케이스

몇 가지 테스트 케이스를 만들어 보겠습니다. 각 자리 수에 대한 결과를 확인하여 함수의 올바른 동작을 검증하겠습니다:

    print("1자리 수: \(countStairNumbers(n: 1))") // 9
    print("2자리 수: \(countStairNumbers(n: 2))") // 17
    print("3자리 수: \(countStairNumbers(n: 3))") // 32
    print("4자리 수: \(countStairNumbers(n: 4))") // X (직접 계산 후 확인)
    print("5자리 수: \(countStairNumbers(n: 5))") // Y (직접 계산 후 확인)

결론

오늘은 스위프트를 이용하여 계단 수 구하기 문제를 해결하는 방법에 대해 알아보았습니다. 우리는 동적 프로그래밍을 통해 이 문제의 효율적인 해결책을 마련할 수 있었습니다. 여러분도 이 문제를 이해하고 활용하여 더 많은 알고리즘 문제를 해결해 보시기 바랍니다!

그럼 다음 시간에 더 흥미로운 주제로 찾아뵙겠습니다. 감사합니다!