[백준/Swift] 2992번: 크면서 작은 수

 

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

2992번: 크면서 작은 수

 

 

x를 구성하는 수로 모든 경우의 수를 진행하면 된다.

경우의 수 중에서 x보다 큰 수 중 가장 작은 수를 찾아야 하므로, answer에 값을 경신하면서 진행

x보다 작은 수는 패스하는 부분을 추가 하지 않았는데, 이 부분을 추가하면 시간이 더 줄어들 것이다.

예를 들어 321라는 수에서 1xx, 2xx는 이미 x보다 크지 않기 때문에 깊게 들어가면 안 된다.

 

516의 경우 탐색된 num 값

0

5

51

516

56

561

1 <- 여기서 끊어냈어야 한다

15

156

16

165

6 <- 여기서 시작하도록

65

651

61

615

561 (answer)

 

여기서 필요 없는 부분은 붉은색 부분인데, 1xx는 이미 500번 대보다 작기 때문에 여기는 들어갈 필요가 없다.

x가 작으면 문제없지만 엄청 크다면... 시간이 오래 걸리겠지

 

한번 적용해 보자!

 

[모든 경우 탐색]-DFS

import Foundation

/*
 정수 X와 구성이 같으면서 X보다 큰 수 중 가장 작은 수 출력하기
 수의 구성이 같다 == 수를 이루고 있는 각 자릿수가 같다는 뜻
 -> 123 == 321, 123 != 432
 */

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

func bt(_ num: Int, _ cnt: Int) {
    if cnt == arr.count {
        if num > x {
            answer = min(answer, num)
        }
        return
    }
    
    for i in 0..<arr.count {
        if !visited[i] {
            visited[i] = true
            bt(num != 0 ? num * 10 + arr[i] : arr[i], cnt + 1)
            visited[i] = false
        }
    }
}
bt(0, 0)
print(answer == Int.max ? 0 : answer)

 

 

[필요 없는 부분 뺀 코드]-Backtracking

import Foundation

/*
 정수 X와 구성이 같으면서 X보다 큰 수 중 가장 작은 수 출력하기
 수의 구성이 같다 == 수를 이루고 있는 각 자릿수가 같다는 뜻
 -> 123 == 321, 123 != 432
 */

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

func bt(_ cnt: Int) {
    if num.count == arr.count {
        let n = Int(num.map{String($0)}.joined())!
        if n > x { answer = min(answer, n) }
        return
    }
    
    var flag = false
    for i in 0..<arr.count {
        if !visited[i] {
            visited[i] = true
            num.append(arr[i])
            if num.count < arr.count {
                for i in 0..<num.count {
                    if num[i] > arr[i] {
                        break
                    }else if num[i] < arr[i] {
                        flag = true
                        break
                    }
                }
            }
            if !flag { bt(cnt + 1) }
            num.removeLast()
            visited[i] = false
            flag = false
        }
    }
}
bt(0)
print(answer == Int.max ? 0 : answer)

 

 

예상했던 것과 다르게 💦

시간은 동일하게 나왔다(12ms). 아마.. X의 크기가 작아서 그런 게 아닌가 싶다..

 

탐색하는 경우의 수를 출력해 보면

 

스크롤에 집중해주세욥

오 그래도 경우의 수가 많이 줄어든 것을 확인할 수 있다. 

좌측이 불필요한 탐색을 한 경우(DFS, 모든 경우의 수 탐색), 우측이 불필요한 탐색은 걷어낸 경우(Backtracking, 조건에 맞는 것만 탐색)

오호라... 조건에 심혈을 기울여서 Backtracking을 구현하도록 노력하자! 시간 줄이기 필수~