백준 9081번(Java)

import java.io.*;

public 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 i=1; i<=T; i++) {
			String word = br.readLine();
			
			// 각 번지의 알파벳 문자를 비교하기 위하여 문자열 배열로 변환
			char[] array = word.toCharArray();
			
			nextPermutation(array);
			System.out.println(array);
		}
	}

	private static void nextPermutation(char[] array) {
		// step1 : a<b를 만족하는 두 수 찾기 → 기준점(인덱스)찾기
		// arr[i] < arr[i+1]
		// 위의 식을 만족하는 것을 찾는데 가장 오른쪽에 있는 것을 선택
		// 그리고 arr[i]의 i가 기준점(피벗)이 됨
		int i = array.length-2;
		
		while(i>=0 && array[i] >= array[i+1]) { // i>=0 : 반복문에서 배열의 인덱스를 벗어나는 참조를 하지 않기 위해
												// array[i] >= array[i+1] → 계속 i값을 감소하며
			i--;								// array[i] < array[i+1] 를 만족하는 인덱스를 찾기 위해
		}
        
        if(i == -1) return;
		
		// step2 : i번지의 값보다 큰 값을 뒤에서부터 찾기 → 찾았으면 swap
		int j = array.length-1;
		
		while(array[i] >= array[j]) {
			j--;
		}
		
		char temp = array[i];
		array[i] = array[j];
		array[j] = temp;
		
		// step3 : i번지 뒤의 숫자들을 오름차순으로 정렬(반전)
		int start=i+1, end=array.length-1;
		
		while(start < end) {
			// 앞뒤 교환
			temp = array[start];
			array[start] = array[end];
			array[end] = temp;
			
			// 시작번지 증가, 끝번지 감소
			start++;
			end--;
		}
	}
}