백준 2992번 : 크면서 작은 수

[백준 온라인 저지 링크]

2992번: 크면서 작은 수

간단한 브루트 포스 문제처럼 보일 수 있지만, N과 M 유형의 백트래킹 문제입니다.

 

주어진 수와 동일한 구성이면서 해당 수보다 처음으로 큰 숫자를 찾아야 하는데요, 여기서 동일한 구성의 수라 함은 각 자리수를 구성하는 수를 재배열해 만들 수 있는 수를 의미합니다.

 

즉, 주어진 수가 176이라면 671이 167과 "구성이 같은 수" 이자 첫 번째로 큰 수가 됩니다.

입력값이 1 ~ 999,999라고 해서 브루트 포스로 풀면 오히려 로직이 더 복잡해지게 되는데요, 최대 자릿수가 6자리인 것을 이용해 각 자리의 수를 백트래킹으로 재조합하면 손쉽게 모든 경우의 수를 탐색할 수 있게 됩니다.

 

[정답 코드 - Python]

X = input()

number = ""
minNumber = "999999"
digit = len(X)
used = [False] * digit

# 최대 자릿수는 6자리이므로, 최대 재귀 깊이도 6이 되어 안정적인 통과가 가능합니다.
def backtrack(depth):
  global number
  global minNumber

  if depth == digit:
  	# 백트래킹 결과가 주어진 수보다 크면서 가장 작은 수가 답이 됩니다.
    if X < number < minNumber:
      minNumber = number
    return

  for i in range(digit):
    # TIP) 여기서 if i in used: 처럼 in 문으로 로직을 작성하면,
    # 다른 문제에서는 시간 초과가 뜰 가능성이 있습니다.
    # 따라서 항상 인덱스를 직접 지정해 해당 배열 요소의 값을 검증해야 합니다.
    
    if used[i] == True: # if i in used: (BAD)
      continue
    used[i] = True
    number += X[i]
    backtrack(depth + 1)
    used[i] = False
    number = number[:-1]


backtrack(0)

if minNumber == '999999':
  minNumber = 0
print(minNumber)