#백준_1342 행운의 문자열 - Java 자바

#유형:탐색, 순열, DFS

# aabbbaa 같은 경우 abababa

# abc => abc acb bac bca cab cba 같이 순열을 만들어서 행운의 문자열인지 체크하면 된다. 

# dfs, 순열의 개념을 알고있었다면 그렇게 어렵지 않은 문제. 시간초과만 주의해주면 된다. 맨 처음에는 순열을 호출할때마다 조건문으로 검사하거나 순열의 파라미터를 String이나 리스트로 넘겼는데, 시간초과가 났다. 그래서 우선 길이에 맞는 순열을 만들때마다 조건문으로 행운의 문자열인지 체크해줘서 count++하면 된다. 이 때 리스트의 첫 번째인덱스부터 다음 인덱스와 같으면 false를 리턴하게 하면 된다.

그리고, 이렇게 짜면 문제점이 중복값이 나온다. aabbbaa 같은 경우에 a가 4개여서 순서가 바뀌어서 중복이 발생하는데, 이 때 팩토리얼로 나눠주면 중복을 없앨수있다.

 

순열 https://ukyonge.tistory.com/16?category=870876

package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
 
public class p1342 {
    static int result=0;
    static String str;
    static ArrayList<Character> arrList = new ArrayList<>();
    static int al[] = new int[26];
    static char arr[] = new char[10];
    static boolean visit[] = new boolean[10];
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        str = br.readLine();
        
        for(int i=0; i<str.length(); i++) {
            al[str.charAt(i)-'a']++;
        }
        
        permutation(0);
        
        for(int i=0; i<26; i++) {
            if(al[i] > 1) {
                result /= factorial(al[i]);
            }
        }
        System.out.println(result);
    }
    public static boolean check() {
        
        for(int i=0; i<arrList.size()-1; i++) {
            if(arrList.get(i)==arrList.get(i+1))
                return false;
        }
        return true;
    }
    public static int factorial(int N) {
        if(N==1)
            return 1;
        
        return N*factorial(N-1);
    }
    public static void permutation(int count) {
        if(count == str.length()) {
            if(check()) {
                result++;
                return;
            }    
        }
        for(int i=0; i<str.length(); i++) {
            if(!visit[i]) {
                visit[i] = true;
                arrList.add(str.charAt(i));
                permutation(count+1);
                arrList.remove(arrList.size()-1);
                visit[i] = false;
            }
        }
    }
}