문제
https://www.acmicpc.net/problem/9081
단어를 입력받아, 그 단어를 이루는 알파벳들로 만들 수 있는 단어들을 사전 순으로 정렬할 때에 주어진 단어 다음에 나오는 단어를 찾는 프로그램을 작성하라.
입력 첫 줄은 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 알파벳 대문자로만 이루어진 단어로 공백은 없다.
풀이
파이썬에서 문자(chr)는 대소 관계 비교가 가능하므로 직전에 풀었던 2022.05.10 - [BOJ] 10972 - 다음 순열(next permutation) 문제를 활용하면 쉽게 풀어낼 수 있다.
차이가 있다면 값의 중복 여부인데, 이는 값을 교환할 위치 i - 1과 j를 찾아내려 갈 때의 조건을 크거나 같을 때 반복하도록 수정하면 된다.
import sys
t = int(sys.stdin.readline())
for _ in range(t):
word = list(sys.stdin.readline()[:-1])
l = len(word)
i = l - 1
while i > 0 and word[i - 1] >= word[i]:
i -= 1
if i <= 0:
print("".join(word))
continue
j = l - 1
while word[j] <= word[i - 1]:
j -= 1
word[i - 1], word[j] = word[j], word[i - 1]
print("".join(word[:i] + word[i:][::-1]))