- 다음 순열 즉,
next_permutation
을 구하는 문제다. 이런 문제는itertools
의permutations
를 사용하면 시간초과(TLE)가 나오기 쉽다.- 이번 문제를 통해서 다음 순열 알고리즘을 익히고 다른 문제에 직접 적용해보면서 연습하는 것도 좋을 것 같다.
다음 순열 구하는 알고리즘은 다음과 같다.
- 오름차순 정렬이 성립되지 않은 시점을 파악하기
- 다음으로 큰 숫자를 찾기
- 교환
- 오름차순 정렬이 성립되지 않는 시점 이후의 부분을 오름차순으로 정렬
import sys
input = sys.stdin.readline
def next_permutations(nums):
i = len(nums) - 1
while i > 0 and nums[i - 1] >= nums[i]:
i -= 1
if i == 0:
msg = 'BIGGEST'
return msg
j = len(nums) - 1
while nums[j] <= nums[i-1]:
j -= 1
nums[i-1], nums[j] = nums[j], nums[i-1]
nums[i:] = reversed(nums[i:])
return nums
T = int(input())
for _ in range(T):
A = list(input().strip())
result = next_permutations(A)
print(''.join(map(str, result)))