백준 9081 단어 맞추기 / python

문제 : 9081

풀이 point

백트래킹을 통해 모든 문자 조합을 구하면 최악의 경우 지수함수 급으로 시간복잡도가 증가하기 때문에 시간초과가 난다.

특정 단어의 바로 다음 단어를 찾는 것이므로 이 단어만 구할 수 있는 함수를 구성하면 된다.

다음 순열 구하기는 다음을 참고한다.

ex) 12345의 다음 순열을 구해보면 21345이다. 즉, 앞에는 바뀌면서 뒤에는 오름차순을 유지하는 것이 목표다. (순열을 순서대로 구하면 이 기조를 띠기 때문이다)

풀이 코드

def next_permunations():
  i = len(arr)-2
  while i >= 0 and arr[i] >= arr[i+1]:
    i -= 1
  pivot = i

  if pivot < 0:
    return None
  
  j = len(arr)-1
  while j > pivot and arr[j] <= arr[pivot]:
    j -= 1
  
  arr[pivot], arr[j] = arr[j], arr[pivot]

  arr[pivot+1:] = reversed(arr[pivot+1:])

  return arr

for _ in range(int(input())):
  string = input()
  arr = list(string)
  value = next_permunations()

  if value == None:
    print(string)
  else:
    print(''.join(arr))