[2992] 크면서 작은 수

생각

• 들어온 수를 정렬
• DFS를 이용하여 모든 조합을 생성한 뒤, X보다 큰 수가 나오자마자 출력하기
  • 오래걸림, 만약 913이 들어왔다면 1xx나 3xx는 의미가 없음
• 백트래킹 이용
  • 만약 현재 자리수보다 작은 수가 들어온다면 중단하고 다른 수를 탐색

백트래킹을 직접 구현해 본 적이 없어서 해당 문제는 답안을 참고하였다.
따라서 해당 블로그의 코드를 분석하겠다.

코드

import Foundation

let x = Int(readLine()!)!
let array = String(x).map{ Int(String($0))! }
var answer = Int.max
var checked = [Bool](repeating: false, count: array.count + 1)
var num = [Int]()

VECI(0)
print(answer == Int.max ? 0 : answer)

//cnt는 현재 몇번째 재귀인지 확인하기 위한 수이므로 생략 가능함
func VECI(_ cnt: Int) {
    //숫자 완성
    if num.count == array.count {
        let n = Int(num.map{String($0)}.joined())!
        //완성한 숫자가 x보다 크다면 기존에 저장되었던 answer과 완성한 숫자를 비교하여 더 작은 수를 answer에 저장
        if n > x { answer = min(answer, n) }
        //재귀형태이므로 return
        return
    }
    
    //유망하지 않으면 flag가 true가 된다.
    var flag = false
    for i in 0..<array.count {
        //들어온 숫자들 중 사용되지 않은 숫자라면
        if !checked[i] {
            //사용한 수로 체크
            checked[i] = true
            //만들고 있는 숫자 배열에 추가
            num.append(array[i])
            //아직 숫자가 완성되지 않았다면
            if num.count < array.count{
                //이번에 추가된 수로 숫자가 유망한지 체크
                for i in 0..<num.count{
                    //유망함(array보다는 큰 수여야 하기 때문)
                    //앞자리 수가 크면 당연히 큰수이기 때문에 바로 break
                    if num[i] > array[i]{
                        break
                    } else if num[i] < array[i] {
                        //유망하지 않음
                        flag = true
                        break
                    }
                }
            }
            //유망하면 다음 수 추가하러 재귀
            if !flag {VECI(cnt + 1) }
            //유망하지 않다면 해당 수를 사용하지 않았던 것으로 돌려둠
            num.removeLast()
            checked[i] = false
            flag = false
        }
    }
}