[BOJ-1342] 행운의 문자열

www.acmicpc.net/problem/1342

 

처음에는 중복을 신경써서 풀어야 하는거 아닌가 생각했지만.

중복은 마지막에 제외해주면 되는 것이고, worst의 경우에는 중복이 일어나는 상황이 아니라

모든 문자열이 다 처음 보는 문자인 경우라서, 시간 복잡도에 영향을 주지 않는다는 것을 깨달았다.

 

package boj.day0323;

import java.util.Arrays;
import java.util.Scanner;

public class BOJ_1342_Main {
	static char[] input;
	static char[] output;
	static boolean[] visited;
	static int ans;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		String s = sc.next();
		input = new char[s.length()];
		int[] alpha = new int[26];
		for (int i = 0; i < s.length(); i++) {
			input[i] = s.charAt(i);
			alpha[s.charAt(i) - 'a']++;
		}
		visited = new boolean[input.length];
		output = new char[s.length()];

		ans = 0;
		permutation(0);
		for (int i = 0; i < alpha.length; i++) {
			if (alpha[i] > 1) {
				ans = ans / factorial(alpha[i]);
			}
		}
		System.out.println(ans);
		sc.close();

	}

	private static int factorial(int n) {
		int r = 1;
		for (int i = n; i >= 1; i--) {
			r = r * i;
		}
		return r;
	}

	private static void permutation(int cnt) {
		if (cnt >= input.length) {
			// if(output[input.length-1]!=output[input.length-2]) {
			for (int j = 1; j < input.length; j++) {
				if (output[j] == output[j - 1]) {
					return;
				}
			}
			ans++;
			System.out.println(Arrays.toString(output));
			return;
		}
		for (int i = 0; i < input.length; i++) {

			if (visited[i])
				continue;

			// if(cnt > 0) {if(input[i] == output[cnt - 1]) continue;}

			visited[i] = true;
			output[cnt] = input[i];
			permutation(cnt + 1);
			visited[i] = false;
		}
	}
}