[Python/BOJ] 16943. 숫자 재배치

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

16943번: 숫자 재배치

문제

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

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

입력

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

출력

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

풀이

Code

import sys
input = sys.stdin.readline

# 1. 백트래킹 함수 정의
def backtracking(number, lst, l) :
    global ans
    # 1-1. 종료 조건 설정
    if not l :
        c = int(''.join(number))
        if c < b :
            print(c)
            sys.exit()
    # 1-2.
    for i in range(l) :
        # 첫 글자가 0인 경우 continue
        if not number and lst[i] == '0' : continue
        # 백트래킹 함수 실행
        backtracking(number + [lst[i]], lst[:i] + lst[i+1:], l-1)

a, b = map(int, input().split())
lst_a = sorted(list(str(a)), reverse = True)
length = len(lst_a)
ans = -1
# 2. 백트래킹 함수 실행
backtracking([], lst_a, length)
# 3. 결과 출력
print(ans)