[백준/Swift] 1038번: 감소하는 수

https://www.acmicpc.net/problem/1038

1038번: 감소하는 수

 

감소하는 수
정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면
예를 들어, 321, 950. 322, 958 안됨. N번째 감소하는 수를 출력하라.

아랫 자릿수로 갈수록 숫자가 작아지면 되는데, 이때 숫자가 같으면 안 된다. 백트래킹으로 앞 원소의 값보다 크거나 같은 수는 잘라냈다.

1자리부터 10자리까지 BT를 진행했다. 감소하는 수를 구했을 경우, 몇번째 감소하는 수인지 나타내는 cnt를 증가시켰다. 만약 내가 원하는 N번째 수라면 출력하고 끝내기.

N번째 수를 출력하고 뒤의 더이상 쓸모없는 수를 구하지 않기 위해서 exit 사용하긴 했는데,,, 사실 이렇게 해도 되는지 잘 모르겠다.. 사실 이렇게 하지 않고, flag 변수를 사용해서 flag가 true라면 더 이상 깊게 들어가지 않도록 해도 된다. 우선 좀 더 찾아보고 많은 사람들이 사용하는지 확인해야겠다ㅎ

 

코드를 확인해보면

import Foundation

//input
let n = Int(readLine()!)!
var visited = [Bool](repeating: false, count: 11)
var cnt = -1

func bt(_ now: Int, _ num: String, _ dest: Int) {
    if now == dest {
        cnt += 1
        if cnt == n {
            print(num)
            exit(0)
        }
    }

    for i in 0...9 {
        if num != "" {
            if String(num.last!) <= String(i) { continue }
        }
        if !visited[i] {
            visited[i] = true
            bt(now+1, num + String(i), dest)
            visited[i] = false
        }
    }
}

for i in 1...10 {
    bt(0, "", i)
}
print(-1)

 

백트래킹 함수는 2가지로 분리되는데, base condition인 끝내는 종료 조건과 원하는 값을 구하기 위해 안으로 들어가는 부분(명확하게 지칭하는 단어를 모르겠네..^^)이 있다. 백트래킹은 만들 수의 자릿수의 개수만큼 실행해 줬다. 즉, 1부터 10자리의 수를 만들 수 있는데 이를 하나씩 넣어서 돌려줬다는 뜻이다.

왜 10 자리 까지냐면 가장 큰 감소하는 수가 9876543210 이기 때문이다! 이게 10자리인데 이것보다 더 큰 감소하는 수는 나올 수 없기 때문에... 그래서 10자리까지 돌려봤는데 N번째 감소하는 수가 나오지 않았다면 -1 출력.

각 자릿수에 들어갈 수 있는 수는 0부터 9뿐이다. 이를 중복 없이(visited 사용) 더 작은 값이 뒤에 붙으면 된다. 더 작은 값만 뒤에 붙을 수 있으므로 앞에서 현재 num의 마지막 원소보다 작은지 확인하고 아니면 패스.

사실 처음엔 10자리까지인지 몰라서 while true로 생각했는데,, 아무리 봐도 아니라ㅋㅋㅋㅋ 좀 더 생각하다 알아차렸다!