[ BOJ ] 16943 : 숫자 재배치 ( SILVER 1 ) / Python

>> 문제 바로가기 (https://www.acmicpc.net/problem/16943)

문제

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

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

입력

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

출력

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

풀이 과정

A에 포함된 숫자를 하나씩 사용하는 백트래킹을 구현한다. 비트마스킹을 통해 어느 숫자를 고르지 않았는지 판별했다.

import sys
input = sys.stdin.readline

a, b = map(int, input().rstrip().split())
a_list = list(str(a))
b_list = list(str(b))
n = len(a_list)

result = -1
def backtracking(vis, now):
    global result
    if vis == (1 << n) - 1:
        a_res = int(''.join(now))
        if a_res < b:
            result = max(result, a_res)
        return
    
    for i in range(n):
        if vis == 0 and a_list[i] == '0': continue
        if ((vis & (1 << (n - 1 - i))) >> (n - 1 - i)) == 0:
            vis |= (1 << (n - 1 - i))
            backtracking(vis, now + [a_list[i]])
            vis ^= (1 << (n - 1 - i))

backtracking(0, [])
print(result)