[Java] 백준 9081 단어 맞추기

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

난이도

실버 1

문제

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

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

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

입력

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

출력

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

코드

import java.util.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for(int t = 0; t < T; t++){
            char[] word = br.readLine().toCharArray();
            next(word);
            System.out.println(new String(word));    
        }
    }

    public static void next(char[] arr){
        int i = arr.length - 1;
        // Step 1. 뒤에서부터 연속된 감소 구간을 찾는다.
        // arr[i-1] < arr[i] 가 되는 i를 찾는다.
        while(i > 0 && arr[i-1] >= arr[i]){
            i--;
        }

		// 이미 가장 마지막 단어인 경우 (내림차순 정렬 상태)
        if(i <= 0) return;

		// Step 2. arr[i-1]보다 큰 가장 마지막 원소 j를 찾아 swap
        int j = arr.length - 1;
        while(arr[i-1] >= arr[j]){
            j--;
        }

		// Step 3. i-1 위치와 j 위치 swap
        swap(arr, i-1, j);

		// Step 4. i부터 마지막까지 reverse 정렬 (오름차순 정렬로 바꿔줌)
        int k = arr.length - 1;
        while(i < k){
            swap(arr, i, k);
            i++;
            k--;
        }
    }

    private static void swap(char[] arr, int a, int b){
        char tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }
}