[ BOJ ][JAVA][9081] 단어 맞추기

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

9081번: 단어 맞추기

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	771	407	342	57.576%

문제

BEER라는 단어를 이루는 알파벳들로 만들 수 있는 단어들을 사전 순으로 정렬하게 되면

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

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

입력

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

출력

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

예제 입력 1

4
HELLO
DRINK
SHUTTLE
ZOO

예제 출력 1

HELOL
DRKIN
SLEHTTU
ZOO

코드

/*
    단어 맞추기
    next permutation
*/
import java.io.*;
import java.util.*;
public class p9081 {
    static int t;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (t-- > 0) {
            sb.append(next(br.readLine())).append("\n");
        }
        System.out.println(sb.toString());
    }

    public static String next(String s){
        if (s.length() == 1) return s;

        int min = 0;
        int idx = 0;

        // 뒤에서부터 탐색하면서 오름차순이 깨지는 인덱스를 확인(idx)
        loop:
        for (idx = s.length() - 2; idx >= 0; idx--) {
            // 다시 뒤에서부터 탐색하면서 idx보다 큰 첫번째 인덱스 를 확인(min)
            for (min = s.length() - 1; min > idx; min--) {
                if (s.charAt(idx) < s.charAt(min)) {
                    break loop;
                }
            }
        }
        if (idx == -1) {
            return s;
        }

        // min과 idx를 스왑
        char[] arr = s.toCharArray();
        char tmp = arr[min];
        arr[min] = arr[idx];
        arr[idx] = tmp;

        // idx에서부터 끝까지 오름차순 정렬
        Arrays.sort(arr, idx + 1, arr.length);

        // String으로 return
        StringBuilder sb = new StringBuilder();
        for (char a : arr) {
            sb.append(a);
        }

        return sb.toString();
    }
}