[BOJ / 백준] 2992 크면서 작은 수 python / 파이썬 백트래킹

출처 : https://www.acmicpc.net/problem/2992

2992번: 크면서 작은 수

---

1) 요구사항 분석 : 문제 읽기

주어진 조건에 맞는 수를 출력

 

2) 설계 : 접근 방식

백트래킹을 이용해서 풀어줌

입력을 배열로 바꿔주고, 그리고 정렬해서 작은 수부터 확인해줌

그리고 큰 수를 찾는 순간 바로 출력 후 함수 종료

# BOJ2992 크면서 작은 수
x = int(input())
arr = list(str(x))
arr.sort()
ans = [0 for _ in range(len(arr))]
visited = [False for _ in range(len(arr))]

def recur(cur):
    if cur == len(arr):
        tem = "".join(ans)
        if int(tem) > x: # 제일 처음 큰 수 찾고 종료
            print(int(tem))
            exit()
        
    for i in range(len(arr)):
        if visited[i]:
            continue

        visited[i] = True

        if cur == 0:
            if arr[i] != 0:
                ans[cur] = str(arr[i])
                recur(cur + 1)
                visited[i] = False
        else:
            ans[cur] = str(arr[i])
            recur(cur + 1)
            visited[i] = False

recur(0)
print(0) # 위에서 함수가 종료가 안되었다면, 그러한 숫자가 없는 경우임