2992 크면서 작은 수

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	2277	1195	999	54.560%

문제

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

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

입력

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

출력

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

예제 입력 1

156

예제 출력 1

165

예제 입력 2

330

예제 출력 2

0

예제 입력 3

27711

예제 출력 3

71127

---

풀이과정

주어진 수에 대해 가능한 순열을 다 구한다.

x보다 작은 것들은 삭제한다.

남은 것들 중 제일 작은 숫자 출력

백트래킹,,,, 으로 못함,,,^^

---

코드

input = list(input())
output = []

def dfs(array, n):
    result = []
    if n==0:
        return [[]]
    for i in range(len(array)):
        new = array[:i]+array[i+1:]
        rest_list = dfs(new, n-1)
        for rest in rest_list:
            result.append([array[i]]+rest)
    return result

new_array = dfs(input, len(input))
for i in new_array:
    if int("".join(i))>int("".join(input)):
        output.append(int("".join(i)))
if len(output)==0:
    print(0)
else:
    print(min(output))