백준 16943 숫자 재배치 Kotlin (순열)

문제 출처 : https://www.acmicpc.net/problem/16943

16943번: 숫자 재배치

문제

두 정수 A와 B가 있을 때, A에 포함된 숫자의 순서를 섞어서 새로운 수 C를 만들려고 한다. 즉, C는 A의 순열 중 하나가 되어야 한다. 

가능한 C 중에서 B보다 작으면서, 가장 큰 값을 구해보자. C는 0으로 시작하면 안 된다.

입력

첫째 줄에 두 정수 A와 B가 주어진다.

출력

B보다 작은 C중에서 가장 큰 값을 출력한다. 그러한 C가 없는 경우에는 -1을 출력한다.

제한

• 1 ≤ A, B < 109

알고리즘 분류

• 수학
• 브루트포스 알고리즘
• 조합론

풀이

간단한 순열 문제이다.

문제 조건에서 헷갈렸던 부분이 있는데,

A에 포함된 숫자의 순서를 섞어서 새로운 수 C를 만든다는 것은 A의 모든 수를 사용하여 C를 만들어야 함을 의미한다.

즉 A와 C의 길이가 같아야 한다.

 

따라서 A에 대한 순열을 구하는데 종료 조건은 A의 길이와 순열 C의 길이가 같을 때이고,

순열 C가 b보다 작다면 정답을 갱신한다.

순열은 문자열로 처리하면 시간이 오래 걸리므로 정수형으로 처리해준다.

 

코드

val br = System.`in`.bufferedReader()
var answer = -1
var result = 0
fun permutation( a: String, b: String, visited: BooleanArray){
    if(result.toString().length==a.length){
        if(result<b.toInt())
            answer = answer.coerceAtLeast(result)
        return
    }

    for(i in a.indices){
        if(visited[i]) continue
        visited[i] =  true
        result = result*10 + (a[i]-'0')
        permutation(a,b,visited)
        visited[i] = false
        result /= 10
    }
}

fun main() = with(System.out.bufferedWriter()){

    val (a,b) = br.readLine().split(' ')
	//a의 길이가 b보다 길다면 c는 모두 b보다 크다
	if(a.length>b.length){
        write("-1")
        close()
        return
    }
    permutation(a,b,BooleanArray(a.length))

    write("$answer")
    close()
}