[백준/Swift] 16943번: 숫자 재배치

 

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

16943번: 숫자 재배치

 

 

• A와 B가 있을 때, A에 포함된 숫자의 순서를 섞어서 새로운 수 C를 만들자.
• C 중에서 B보다 작으면서 가장 큰 수 구하기
• 0으로 시작하면 안 됨

이 문제가 까다로웠던 것은 문자열과 숫자와의 변환이 헷갈려서!

0으로 시작하면 안 되니까 그것도 체크해줘야 한다!

 

 

우선 모든 순열을 구해봤다.

아슬아슬하게 통과..

 

[모든 순열을 구한 경우] -> 676ms 🚨

import Foundation

//input
let ab = readLine()!.split(separator: " ").map{ String($0) }
let (a, b) = (ab[0].map{ Int(String($0))! }, Int(ab[1])!)
var visited = [Bool](repeating: false, count: a.count+1)
var result = -1

func bt(_ now: Int, _ num: [Int]) {
    if now == a.count && num[0] != 0 { //새로운 순열 완성
        let n = Int(num.map({ String($0) }).joined())!
        if b > n {
            result = max(result, n) //가장 큰 값
        }
        return
    }
    
    for i in 0..<a.count {
        if !visited[i] {
            visited[i] = true
            bt(now+1, num + [a[i]])
            visited[i] = false
        }
    }
}

func solution(){
    bt(0, [])
    print(result)
}

solution()

 

통과한 다음에 다시 생각해 봤다. 내가 시간이 제일 오래 걸렸던데,,, 다들 어떻게 했을까?ㅠ

조금 찾아보니 역순으로 먼저 정렬하고 진행했다!

생각해 보니 정말... 이렇게 하면 굳이 필요 없는 앞의 수를 만들어줄 필요가 없다.

맨 뒤에서 시작해서 B보다 작으면 바로 출력하고 끝!

더 생각하고 문제를 풀자~

 

[B보다 작은 애들 중 가장 큰 애를 고를 거니까, 역순으로 정렬해서 시작] → 112ms

import Foundation

//input
let ab = readLine()!.split(separator: " ").map{ String($0) }
let a = ab[0].map{ String($0) }.sorted(by: >)
let b = Int(ab[1])!
var visited = [Bool](repeating: false, count: a.count+1)

func bt(_ now: Int, _ tmp: String) {
    if now == a.count {
        if Int(tmp)! < b {
            print(tmp)
            exit(0) //바로 끝내버리기 (더이상 재귀호출하지 않고 바로 끝내기 -> 프로그램 종료)
        }
        return
    }
    
    for i in 0..<a.count {
        if now == 0 && a[i] == "0" { continue } //0으로 시작하면 패스
        if !visited[i] {
            visited[i] = true
            bt(now+1, tmp + a[i])
            visited[i] = false
        }
    }
}

bt(0, "")
print(-1)