2992. 크면서 작은 수

업데이트 시간 : 2023-02-20 05:04:55 +0000

[Silver III] 크면서 작은 수 - 2992

문제 링크

성능 요약

메모리: 31256 KB, 시간: 40 ms

분류

백트래킹(backtracking), 브루트포스 알고리즘(bruteforcing), 문자열(string)

문제 설명

정수 X가 주어졌을 때, X와 구성이 같으면서 X보다 큰 수 중 가장 작은 수를 출력한다.

수의 구성이 같다는 말은, 수를 이루고 있는 각 자리수가 같다는 뜻이다. 예를 들어, 123과 321은 수의 구성이 같다. 하지만, 123과 432는 구성이 같지 않다.

입력

첫째 줄에 X가 주어진다. (1 ≤ X ≤ 999999) X는 0으로 시작하지 않는다.

출력

첫째 줄에 결과를 출력한다. 만약 그러한 숫자가 없는 경우에는 0을 출력한다.

💡 Solutions

📄 크면서 작은 수.py

N = input()
n = int(N)

n_lst = list(map(int, list(N)))

size = len(n_lst)
is_used = [False for _ in range(size)]
n_lst.sort()

# 156 = 100 + 50 + 6
rlt = 0
def bt(depth, target, ans):    
    global rlt
    if depth == (size+1):
        if ans > target:
            rlt = ans
            return True
        return False

    for i in range(len(n_lst)):
        if is_used[i] : 
            continue
        a = n_lst[i] * 10**(size - depth)
        t = target - target%10**(size-depth)

        if a + ans < t:
            continue 
        
        ans += a
        is_used[i] = True
        trigger = bt(depth+1, target,ans)

        if trigger:
            return True

        is_used[i] = False
        ans -= a

bt(1, n, 0)
print(rlt)