[Python] BOJ 9081 - 단어 맞추기

https://www.acmicpc.net/problem/9081

9081번: 단어 맞추기

# C++ STL에는 next_permutation 메소드가 있지만, java나 Python에는 존재하지 않아

   직접 구현을 해주었다.

 

# https://hanil0623.tistory.com/2 <- 구현은 이 블로그를 참조했다.

[C++ STL] next_permutation의 내부 구현 방법

 

* next_permutation함수

    1. k = -1로 설정하고 반복문을 돌며 s[i] < s[i+1]를 만족하는 최대 i를 찾아 k에 넣어준다.

        마지막까지 k가 -1이라면 문자열s가 오름차순이므로 사전순으로 정렬했을때 마지막 단어이다.

        따라서 False를 return해준다.

 

    2. k를 찾아주고 이번에는 마지막 인덱스부터 0번째 인덱스까지 반복문을 돌며 s[k]보다 큰 값(s[i])를

        찾아준다. s[k] < s[i]를 만족하는 i를 발견했으면 m에 i를 넣어주고 바로 break를 해준다.

 

    3. s[k]와 s[m]의 위치를 바꿔준 뒤, L에 s[0 : k+1]까지 넣어준다.

       그 뒤에 s[k+1: ]을 reverse해준 list를 extend해준뒤 L을 return해준다.

 

* 테스트케이스마다 문자열 s를 받아 next_permutaion(list(s))를 실행해준다.

   answer가 True이면 사전순으로 정렬한 다음 단어인 answer를 출력해주고

   False이면 마지막 단어이므로 s를 그대로 출력해준다.

 

import sys
input = sys.stdin.readline

def next_permutation(s):
    k = -1
    for i in range(len(s) - 1):
        if s[i] < s[i+1]:
            k = i
    if k == -1:
        return False

    for i in range(len(s)-1, -1, -1):
        if s[k] < s[i]:
            m = i
            break

    s[k], s[m] = s[m], s[k]
    L = s[ :k+1]
    L.extend(list(reversed(s[k+1: ])))
    return L


N = int(input())
for _ in range(N):
    s = input().rstrip()
    answer = next_permutation(list(s))
    if answer:
        print(''.join(answer))
    else:
        print(s)