[백준 9081] 단어 맞추기 (python)

9081번: 단어 맞추기

---

 

c++에는 algorithm 헤더에 next_permutation이라는 함수가 있다고 한다. 파이썬에서는 없으니 구현하는 수 밖에 없다.

원리를 찾아보니 이해하기 어려워 정리를 한다.

예시: 136541

1. 끝에서부터 비교해 앞에것이 더 작은 곳을 i로 정한다. (3 < 6)

2. 끝에서부터 i값보다 큰 값을 찾아 j로 정한다. (3 < 4)

3. i값과 j값을 서로 바꾼다.

4. i뒤에 있는 것들을 순서를 뒤집어준다.

답: 141356

 

import sys
input = sys.stdin.readline


def nextPermutation(arr):
    i = len(arr)-2
    while i >= 0 and arr[i] >= arr[i+1]:
        i -= 1
    if i == -1:
        return False

    j = len(arr)-1
    while arr[i] >= arr[j]:
        j -= 1

    arr[i], arr[j] = arr[j], arr[i]
    result = arr[:i+1]
    result.extend(list(reversed(arr[i+1:])))
    return result


T = int(input())
for _ in range(T):
    _input = list(input().rstrip())
    answer = nextPermutation(_input)
    if not answer:
        print("".join(_input))
    else:
        print("".join(answer))