BOJ_9081 [ 단어 맞추기 ]

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

9081번: 단어 맞추기

 

문제 풀이

 

 주어진 문자에 다음 문자를 찾는 문제이다.
 다음 문자를 찾기 위해서 알파벳 간에 비교를 통해 변경할 위치를 찾는다.
 

변경할 위치가 i,j 라면 

 i는 arr[i-1] < arr[i] 조건에 해당되는 i 최댓값을 찾는다.
 j는 arr[i-1] < arr[j] 조건에 해당되는 j 최댓값을 찾는다.

그 후 arr[i-1] <-> a[j] 알파벳 변경 위치를 변경한다.

arr[i:] 이후 문자 오름차순 정렬 후 붙이면 된다.

 

 

정답 소스 

from sys import stdin

for t in range(int(stdin.readline())):
    inputString = list(stdin.readline().rstrip())
    length = len(inputString)
    i, j = 0, 1
    # 바꿀 위치 찾는다.
    for idx in range(1, length):
        if inputString[idx] > inputString[idx - 1]:
            if i < idx:
                i = idx
    for idx in range(1, length):
        if inputString[idx] > inputString[i - 1]:
            if j < idx:
                j = idx

    if i != 0 and j != 0:
        inputString[i-1], inputString[j] = inputString[j], inputString[i-1]
        inputString[i:] = sorted(inputString[i:])
    print(''.join(inputString))