[알고리즘/Swift] BOJ 1038 감소하는 수 - 완전 탐색

이미지를 누르면 문제로 연결됩니다.

🤔 문제 유형 :: 브루트포스(완전탐색) / 백트래킹

---

💡 풀이 방법

✔︎ 감소하는 수가 어떻게 구성되는지 먼저 생각해본다.

👉 n 자리의 숫자라면 첫째 자리가 고정되어있을 때, 두번째는 첫째 자리보다 작은 값으로, 세번째는 두번째 자리보다 작은 값으로, n번째 자리는 n-1 번째 자리보다 작은 값으로 구성된다.

 

✔︎ 문제를 풀면서 참고해야 하는 사항들

 

• 감소하는 수의 최대값은 9876543210으로, 최대 자리수는 10자리이다.
• 감소하는 수의 최소값은 0으로, 최소 자리수는 1이다. 
• 감소하는 수의 개수는 1022개이다. N = 1023 부터는 -1을 출력해야 한다.

 

✔︎ 풀이를 정리하자면 ?!

 

• 자리 수를 지정하고, 자리수에 따라 감소하는 수를 찾는다. --- 0 부터 9까지 반복한다. (혹은 1 ~ 10)
• 0번째 자리에 0 ~ 9 까지의 숫자를 고정시키고, DFS 를 통해 1..<n 번째 자리의 값을 찾는다.
• DFS 에서는 현재까지 채워진 자리의 값보다 작은 값들로 다음 값을 대입시킨다.
• DFS 종료는 채워진 자리수가 지정된 자리수보다 크거나 같은 경우 종료되며, 이 때 감소하는 수 배열에 값을 추가한다. 

 

👀 Swift 풀이

struct BOJ_1038 {
    
    var decreasingNumbers: [Int] = []
    
    /// j 번째 자리의 값을 채워가며 number 배열을 완성하는 함수, i 번째 자리까지 다 차면 decreasingNumbers 에 추가한다.
    mutating func dfs(_ i: Int, _ j: Int, number: [Int]) {
        // i 는 숫자의 자리수, j 는 현재까지 채워진 자리수
        if j >= i {
            let intNumber = number.reduce(0, {$0*10 + $1})
            decreasingNumbers.append(intNumber)
            return
        }
        for k in (0..<number[j]).reversed() {
            var newNumber = number
            newNumber[j+1] = k
            dfs(i, j+1, number: newNumber)
        }
    }
    
    /// N 번째 감소하는 수를 찾는 함수
    mutating func findDecreasingNumbers(_ N: Int) {
        // i 는 숫자의 자리수, num 은 0번재 숫자로 지정할 값
        for i in 0...9 {
            for num in 0...9 {
                var number = Array(repeating: 0, count: i+1)
                number[0] = num
                dfs(i, 0, number: number)
            }
        }
        decreasingNumbers.sort()
        if N >= decreasingNumbers.count {
            print(-1)
        } else {
            print(decreasingNumbers[N])
        }
    }

    mutating func run() {
        let N = Int(readLine()!)!
        findDecreasingNumbers(N)
    }
}
var boj = BOJ_1038()
boj.run()

---

✏️ 참고할 문법

정수형 배열 [Int] 를 배치된 순서대로 정수형 숫자 Int 로 바꾸는 방법

let intNumber = number.reduce(0, {$0*10 + $1})

Concatenate Swift Array of Int to create a new Int