백준 9081 : 단어 맞추기

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

9081번: 단어 맞추기

 

해결 방법 : 구현

• 사전순으로 다음으로 올 단어를 어떻게 판단할지, 로직을 짜야한다.
  • permutation으로 구하면 최대 10! 개의 단어들이 생성 될 것이다.
• 사전순으로 더 늦게 나오는 단어가 되기 위해서는, 단어의 가장 마지막부터 양옆 문자를 비교하다가,
  • word[i-1] < word[i] 인 경우가 생긴다면 word[i-1]이 뒤로 가야 한다. 
  • i-1번째 문자는 word[i-1]보다 큰 최소의 문자가 되어야 한다.
  • 나머지는 사전순 정렬해야 한다.

 

import sys
input = sys.stdin.readline

def solution(word):
    for i in range(len(word)-1, 0, -1): # 마지막 문자들 부터 비교
        if word[i-1] < word[i]: # word[i-1]이 변경점
            order = sorted(list(word[i-1:])) 
            for c in order: # word[i-1] 보다 큰 최소의 문자를 찾는다.
                if word[i-1] < c:
                    order.remove(c) # word[i-1]을 대체할 문자 'c'를 한개 제거
                    return word[:i-1] + c + ''.join(order)

    return word

if __name__ == '__main__':
    T = int(input())
    for _ in range(T):
        word = input().strip()
        result = solution(word)
        print(result)