[BOJ] 9081번 단어 맞추기 (Python)

📃 문제

[BOJ] 단어 맞추기 🔗링크

다른 문제를 풀다가 next permutation 알고리즘을 알게 되었고,
해당 알고리즘을 이용해 새로운 문제를 풀어보고자 이 문제를 풀었다.

🧠❓ 문제 접근 및 풀이

🐶 1번째 접근

단순히 next permutation 알고리즘을 적용하면,
다음에 나올 문자열(=답)을 찾아낼 수 있다.

import sys
input = sys.stdin.readline

def next_perm(w):
    for i in range(len(w)-1, 0, -1):
        if w[i-1] < w[i]:
            for j in range(len(w)-1, i-1, -1):
                if w[i-1] < w[j]:
                    w[i-1], w[j] = w[j], w[i-1]
                    return (w[:i] + (w[i:][::-1]))
    return w

T = int(input())
for _ in range(T):
    w = list(input().strip())
    ans = ''.join(next_perm(w))
    print(ans)