[백준 2992] 크면서 작은 수 - python

💡문제 분석 요약

문제

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

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

입력

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

출력

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

💡알고리즘 설계

1. permutations으로 해당 숫자들로 구성할 수 있는 모든 숫자의 조합을 구한다.
2. 내림차순으로 정렬한다.
3. 조합의 숫자들을 하나씩 순회하며, 기존 입력받은 숫자보다 작은 숫자가 있을 경우 그 이전 숫자를 프린트한다.

💡코드

from itertools import permutations

num = list(input())
numbers = list(permutations(num, len(num)))
numbers.sort(reverse=True)

result = [ "".join(n) for n in numbers]
strNum = "".join(num)
answer = 0

for n in result:
  if n<=strNum:
    break
  else:
    answer = n

print(answer)

💡 느낀점 or 기억할 정보

모든 조합 구하기: permutations

백트래킹으로도 풀 수 있었을 것 같은데, 시도해보지 못했다.