백준 - 애너그램

문제 설명

입력받은 문자열의 모든 철자로 만들수 있는 길이 n의 문자를 출력하는 문제이다.

각 철자들을 중복될 수 있으며 같은 만들 수 있는 단어는 반드시 한번만 출력해야 한다. 또한 알파벳 순서대로 출력을 해야한다.

TRY

일반적인 DFS [메모리 초과]

순열 - Next-Permutation [성공]

순열을 사전 순서대로 뽑으려고 할때 지금 뽑은 순열의 다음순열이 어떤 것인지 알아내는 알고리즘이다.

1. 증가하는 구간 찾기
2. 오른쪽구간에 큰값과 SWAP하기
3. 다시 오른쪽구간 재정렬하기

풀이

private static char[] arr;

	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(reader.readLine());
		StringBuilder answer = new StringBuilder();

		while (n-- > 0) {
			arr = reader.readLine().toCharArray();

			Arrays.sort(arr);
			answer.append(arr).append("\\n");

			while (isNextWords(arr.length)) {
				answer.append(arr).append("\\n");
			}
		}

		System.out.println(answer);
	}

	/**
	 * next-permutation 알고리즘
	 * @param n - 단어의 길이
	 */
	static boolean isNextWords(int n) {
		int idx = n - 1;
		
		// 증가하는 구간 찾아내기
		while (idx > 0 && arr[idx] <= arr[idx - 1]) {
			idx--;
		}

		// 사전순으로 마지막이다 ex) 4321
		if (idx == 0) {
			return false;
		}
		
		// 오른쪽 구간에서 큰 값 찾고 스왑하기
		for (int i = n-1; i >= idx; i--) {
			if (arr[idx - 1] < arr[i]) {
				char temp = arr[i];
				arr[i] = arr[idx - 1];
				arr[idx - 1] = temp;
				break;
			}
		}
		
		// 오른쪽구간에서 큰값과 스왑했으니 다시 재정렬하기
		Arrays.sort(arr, idx, n);
		return true;
	}