[알고리즘/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])
}