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

---

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

---

풀이

문제를 읽으면 알 수 있다시피 '다음 순열' 알고리즘을 이용하면 해결되는 문제이다.

다음 순열 알고리즘은 비법이 따로 있으니 참고해보면 좋다.
https://velog.io/@iamjinseo/백준-10972-다음-순열

알고리즘
단어 -> to charArray -> 정렬
정렬된 리스트에 대해 다음 순열 찾기 실행
// 예) 12543 -> 13542 -> 13245

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

public class B9081_단어맞추기 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		StringBuilder sb =new StringBuilder();
				
		int T = sc.nextInt();
		sc.nextLine();
		for (int t = 1; t <= T; t++) {
			char[] str = sc.nextLine().toCharArray();
			sb.append(String.valueOf(np(str))).append('\n');
		}
		System.out.println(sb);
	}
	static char[] np(char[] str) { //다음 순열 알고리즘
		for (int i = str.length-1; i >= 1; i--) {
			if(str[i]>str[i-1]) { //꼭대기 지점(i) 찾기
				for (int j = str.length-1; j >= 1; j--) { 
					if(str[j]>str[i-1]) { // i-1에 있는 것보다 더 큰 문자가 있으면
						char temp = str[i-1];
						str[i-1] = str[j];
						str[j] = temp; 
						// end swap
						
						str = swapLast(str, i);
						return str;
					}
				}
			}
		}
		return str;
	}
	static char[] swapLast(char[] str, int i) {
		int lastIdx = str.length-1;
		for (int j = i; j <= (i+str.length-1)/2; j++) {
			char temp = str[j];
			str[j] = str[lastIdx];
			str[lastIdx--] = temp;
		}
		return str;
	}
}

np함수는 다음 순열 알고리즘이다.

swapLast는 꼭대기 앞부분과 그거보다 큰 숫자를 뒤에서 찾아 서로 바꾼 후, 꼭대기부터의 문자열을 뒤집어야 할 때가 있는데, 그 때 쓰는 함수이다.

---

꼭대기 문자~끝 문자의 중간 길이까지 탐색하며, 대칭되는 위치에 있는 문자를 바꾼다. 그러면 뒤집힌다
예시) 4321 -> 1324 -> 1234

---

결과