[백준] 2697번 다음수 구하기

💡문제접근

• 다음 순열 즉, next_permutation을 구하는 문제다. 이런 문제는 itertools의 permutations를 사용하면 시간초과(TLE)가 나오기 쉽다.
• 이번 문제를 통해서 다음 순열 알고리즘을 익히고 다른 문제에 직접 적용해보면서 연습하는 것도 좋을 것 같다.

다음 순열 구하는 알고리즘은 다음과 같다.

• 1. 오름차순 정렬이 성립되지 않은 시점을 파악하기
• 2. 다음으로 큰 숫자를 찾기
• 3. 교환
• 4. 오름차순 정렬이 성립되지 않는 시점 이후의 부분을 오름차순으로 정렬

💡코드(메모리 : 31256KB, 시간 : 36ms)

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)))

💡소요시간 : 40m