[백준 9081번] 파이썬 - 단어 맞추기

백준 9081 - 단어 맞추기

시간 제한 1초, 메모리 제한 128MB

# 조건

• BEER라는 단어를 이루는 알파벳들로 만들 수 있는 단어들을 사전 순으로 정렬하게 되면 아래와 같이 된다.

BEER
BERE
BREE
EBER
EBRE
EEBR
EERB
ERBE
EREB
RBEE
REBE
REEB

• 이러한 순서에서 BEER 다음에 오는 단어는 BERE가 된다.
• 이와 같이 단어를 주면 그 단어를 이루는 알파벳들로 만들 수 있는 단어들을 사전 순으로 정렬할 때에 주어진 단어 다음에 나오는 단어를 찾는 프로그램을 작성하시오.

입력

• 입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 10)가 주어진다.
• 각 테스트 케이스는 하나의 단어가 한 줄로 주어진다.
• 단어는 알파벳 A~Z 대문자로만 이루어지며 항상 공백이 없는 연속된 알파벳으로 이루어진다. 단어의 길이는 100을 넘지 않는다.

출력

• 각 테스트 케이스에 대해서 주어진 단어 바로 다음에 나타나는 단어를 한 줄에 하나씩 출력하시오.
• 만일 주어진 단어가 마지막 단어이라면 그냥 주어진 단어를 출력한다.

# 접근 방법

• 주어진 단어로 이루어진 모든 순열을 생성한다면, 메모리 초과가 발생한다.
• 따라서 C++에 있는 next_permutation을 python에서 구현해줌으로서 풀었다.
• next_permutation의 로직은 아래와 같다.
  • 끝에서부터 순회하며 앞에 단어가 더 작은 곳을 i로 정한다.
  • 끝에서 부터 i값보다 큰 j 값을 찾는다.
  • i와 j를 바꾸고 i 뒤에 있는 값을 뒤집어준다.
• 참고 - https://hillier.tistory.com/102

import sys
sys.stdin = open('input.txt')
input = sys.stdin.readline

def next_permutation(arr):
    i = len(arr)-2
    while i >= 0 and arr[i] >= arr[i+1]:
        i -= 1
    if i == -1:
        return False

    j = len(arr) -1
    while arr[i] >= arr[j]:
        j -= 1
    arr[i], arr[j] = arr[j], arr[i]
    result = arr[:i+1]
    result.extend(list(reversed(arr[i+1:])))
    return result


T = int(input())
for _ in range(T):
    target = list(input().strip())
    res = next_permutation(target)
    if not res:
        print("".join(target))
    else:
        print("".join(res))