단어 맞추기

작성일 | 분류 , |
알파벳 단어들을 사전 순으로 정렬 한다면 다음 단어는 현재 단어들에서 최소한으로 변화시켜야 합니다.

알파벳 단어들을 사전 순으로 정렬 한다면 다음 단어는 현재 단어들에서 최소한으로 변화시켜야 합니다.

A B C D 다음에 A B D C 는 시전 순으로 최소한 변화를 준 단어입니다.

최소의 변화를 주기 위해서는 최대한 뒤쪽의 알파벳들을 자리를 변경 시키면 될 것 같습니다.

A B D C 의 다음 단어는 A C B D 입니다. C가 뒤에서 부터 앞의 단어 D swap 또 한번 C가 B와 swap 한 것으로 보입니다.

A C B D 다음은 A C D B 입니다. C, D 를 통해서 유추 할 수 있는 부분은 A B D C 경우에서 C는 뒤에서 앞으로 가면서

자신보다 작은 경우를 만나는 첫번째 경우 까지 swap 한다. A C B D의 경우 D도 동일하다. 그럼 A C D B 도 B를 뒤로 가면서

자신보다 작은 경우를 처음으로 만나는 경우까지 간다면 B A C D 가 된다. 그런데 저 경우는 틀린 경우다. A D B C 이런 경우가 아직 있다.

무엇인가 규칙은 존재하는 것 같지만 찾기가 쉽지는 않습니다.

규칙을 찾아라

A B D C 의 경우에서 다음 경우를 위해서는 C가 B 자리에 가야 합니다. A까지는 가면 안됩니다. 차례 차례 swap 아니라 C 와B 만 swap 해봅니다.

A C D B 가 됩니다. 그런데 A C B D 를 무시하게 됩니다. 그래서 D, B도 자리를 swap 해줘야 합니다.

C 위치, B 위치 찾고 C가 새로 위치한 자리 뒤에서 부터 최소한의 변화를 위해서 자리 이동이 필요해 보입니다.

A B D C (B, C swap)-> A C D B (D, B swap)-> A C B D

한번더 A C B D (B, D swap) -> A C D B (B swap 대상이 없음) -> A C D B

하지만 A C D B 다음 단어는 위 방식으로 적용되지 않습니다. A D B C

아래 그림을 보고 유추해봅시다.

  1. 자리를 swap 될 때 바로 인근 자리끼리 이동 하는 경우

  2. 자리를 swap 될 때 몇 자리 옆을 이동 하는 경우 그리고 제일 뒤에서 부터 앞으로 오게된 자리 뒤 까지 연속 swap 되고 있습니다.

  3. 의 경우 뒤으로 가야하는 알파벳과 앞으로 가야 하는 알파벳의 조건은 찾아보자

뒤로 가야 하는 알파벳은 현 위치와 다음 위치의 알파벳 사전 순서가 다음 위치가 큰 경우의 마지막 번째 알파벳 (I 번째)

A B D C 의 경우 A < B , B < D B의 위치

앞으로 가야 하는 알파벳은 I 번째 위치의 알파벳보다 사전 순서가 뒤인 경우의 마지막 위치

A B C D 의 경우 B 보다 사전 순서가 뒤인데 마지막 위치한 D 와 swap 합니다.

A D C B 로 순서를 변경 2.를 진행 D 이후 swap A D B C

/**
 * 제목 : 단어 맞추기
 * 링크 : https://www.acmicpc.net/problem/9081
 * 분류 : Next Permutation
 */
public class Main {

	public static void main(String[] args) {
		var sc = new Scanner(System.in);
		var sb = new StringBuilder();
		var t = sc.nextInt();
		for (int i = 0; i < t; i++) {
			sb.append(nextPermutation(sc.next()) + "\n");
		}
		System.out.println(sb.toString());
	}

	private static String nextPermutation(String word) {
		var i = word.length() - 1;
		while (i > 0 && word.charAt(i - 1) >= word.charAt(i)) {
			i--;
		}
		if (i <= 0) return word;

		var j = word.length() - 1;
		while (word.charAt(j) <= word.charAt(i - 1)) {
			j--;
		}
		var arr = word.split("");
		swap(i - 1, j, arr);

		j = word.length() - 1;
		while (i < j) {
			swap(i, j, arr);
			i++;
			j--;
		}

		return Arrays.stream(arr).collect(Collectors.joining());
	}

	private static void swap(int i, int m, String[] str) {
		var temp = str[i];
		str[i] = str[m];
		str[m] = temp;
	}
}