백준 - 9081 번 단어 맞추기

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main_9081_단어맞추기 {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int testCase = Integer.parseInt(br.readLine());
		for(int i=1; i<=testCase; i++) {
			String word = br.readLine();
			//각번지의 알파벳 문자를 비교하기 위하여 문자열 배열로 변환
			char [] array =word.toCharArray();
			
			nextPermutation(array);
			
			System.out.println(new String(array));
		}
		
        br.close();
	}//main

	private static void nextPermutation(char[] array) {
        // Step 1:   a<b 를 만족하는 두 수 찾기!! ==> 기준점(인덱스) 찾기
        //         arr[i]<  arr[i+1]
        //         위의 식을 만족하는 것을 찾는데 가장 오른쪽에 있는것을 선택
        //        그리고 arr[i]의 i가 기준점(피벗)이 된다!!
		int i=array.length-2;
		/*
		 ------------------
		 D   R   I   N   K
		 ------------------
index    0   1   2   3   4
		 
		 ------------------
		 B   O   O
		 ------------------
index    0   1   2 

		 
		 */
		while(i>=0 &&  array[i]  >=  array[i+1] ) {   //i>=0 : 반복문에서 배열의 인덱스를 벗어나는 참조를 하지 않기 위해
						
			                                     //array[i]  >=  array[i+1]   ==> 계속 i값을 감소하며
			                                     //array[i]  <  array[i+1] 를 만족하는 인덱스를 찾기 위해
			i--;
		}
		
		//다음 순열이 없다면  (전체 내림차순이라면)
//		if(i==-1)return;
		if(i<0)return;
		
 
        // Step 2: i번지의 값보다 큰값을 뒤에서 부터 찾기!!  ==>찾았으면 swap
		int j=array.length-1;
		while(array[i] >= array[j] ) {
			j--;
		}

		char temp = array[i];
		array[i]  = array[j];
		array[j]  = temp;
		
		
        // Step 3: i번지 뒤의 숫자들을 오름차순으로 정렬 (반전)
		int start=i+1 , end=array.length-1;
		while(start < end) {
			//앞뒤 교환
				temp     = array[start];
			array[start] = array[end];
			array[end]   = temp;
			
			//시작번지 증가,  끝번지 감소
			start++;  end--;
		}
		
//4
//HELLO
//DRINK
//SHUTTLE
//ZOO

	}

}