[알고리즘/Swift] 1038 감소하는 수

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 1038 감소하는 수
• 제출 언어: Swift
• 알고리즘 분류:
• 브루트포스 알고리즘
• 백트래킹

---

풀이

이 문제를 한참 읽어도 이해가 가지 않았는데 이해한 바로는
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 21, 30, 31.. 등 처럼 자리수가 작아질 때마다 수도 감소하는 수를 감소하는 수라고 한다
즉 10은 10번째 감소하는 수이고, 20은 11번째 감소하는 수이다

알고리즘 설계

일의 자리 숫자중 감소하는 수는 0~9이고
십의 자리 숫자중 감소하는 수는 10, 20, 21, 30, 31, 32, 40 ..이다
백의 자리 숫자중 감소하는 수는 210, 310, 320, 321등이다
내가 생각한 알고리즘은 이중 배열 arr를 만들어서 첫번째 배열은 0~9 값을 넣어놓고
십의 자리부터 이전 자리에 있는 값들을 돌면서 그 수의 첫번째 자리보다 큰 값을 넣어서 minArr배열에 놓고 이 배열을 정렬한 후, arr배열에 넣는다
이때, 감소하는 수중에 가장 큰 값은 9876543210 이므로 1022번째 감소하는 수이므로 N > 1022일 경우에는 -1을 출력한다

while count <= N {
    var minArr : [Int] = []
    for j in arr[i] {
        let str = String(j)
        let num = Int(String(str[str.startIndex]))!
        if num < 9 {
            for k in num+1...9 {
                minArr.append(Int(String(k) + String(j))!)
            }
        }
    }
    if minArr.isEmpty {
        break
    }
    i += 1
    arr.append(minArr.sorted(by: <))
    count += minArr.count
}

전체 코드

import Foundation

let N = Int(readLine()!)!
var arr : [[Int]] = []

arr.append([0,1,2,3,4,5,6,7,8,9])
var count = 9
var i = 0

while count <= N {
    var minArr : [Int] = []
    for j in arr[i] {
        let str = String(j)
        let num = Int(String(str[str.startIndex]))!
        if num < 9 {
            for k in num+1...9 {
                minArr.append(Int(String(k) + String(j))!)
            }
        }
    }
    if minArr.isEmpty {
        break
    }
    i += 1
    arr.append(minArr.sorted(by: <))
    count += minArr.count
}

if N > 1022 {
    print(-1)
}
else {
    print(arr.flatMap({$0})[N])
}