[Java] BOJ 1342 행운의 문자열

1342번: 행운의 문자열

---

정답 코드

• 배열에 알파벳 수 저장
• 지난 알파벳과 비교해서 자른 문자열만 재귀적으로 탐색 

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

public class Main {

    static BufferedReader br;
    static StringTokenizer st;
    static String str;
    static int[] arr;
    static int N, cnt;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        str = br.readLine();
        N = str.length();

        arr = new int[26];
        for (char c : str.toCharArray()) {
            arr[c - 'a']++;
        }

        fun(0, -1);

        System.out.println(cnt);
    }

    private static void fun(int index, int last) {
        if (index == N) {
            cnt++;
            return;
        }

        for (int i = 0; i < 26; i++) {
            if (arr[i] == 0 || last == i) {
                continue;
            }
            arr[i]--;
            fun(index + 1, i);
            arr[i]++;
        }
    }
}