백준- 행운의 문자열 자바/java

정말 어이가없는건..c++할때는 뭐가 좋은지 몰랐는데

갑자기 순열을 많이 쓰게 되면서 c++의 좋은점을 깨달았다..next permutation을 사용할 수 있는 것인데

자바에서는 그냥 구현해줘야 한다..ㅎ

그래도 뭐

직접 구현해야 실력도 늘지..

 

- 먼저 각 알파벳 종류와 개수를 map에 저장해주었다. -> 이건 나중에 나눠줄때 필요해서

- 그다음 모든 순열 조합을 찾아내고 -- 순열 찾는건 다른 글에 있으니 그걸 찾아보도록/ 블로그에도 많이 있다.

- 찾아낸 조합은 행운의 문자열인지를 체크해준다. - check()함수

- 행운의 문자열의 개수를 센다 - count로

-마지막으로 count를 각 알파벳 개수의 팩토리얼로 나눠준다.

=> ex) aabc일때  a(첫번째 a)ba(두번째 a)c 와 a(두번째 a)ba(첫번째 a)c 는 분명 코드상에서는 다르다고 하지만

사실은 같기때문에 중복이 생긴다! 그래서 그걸 팩토리얼을 사용해 나눠줘야한다. --> 사실 이걸 생각해내면 문제는 쉽다

import java.util.Scanner;
import java.util.HashMap;

public class Main
{
    static int count=0;
    static void perm(int depth, String[] arr){
        if(depth == arr.length){
            check(arr);
            return ;
        }
        for(int i=depth; i<arr.length;i++){
            swap(arr,i,depth);
            perm(depth+1,arr);
            swap(arr,depth,i);
        }
    }
    static void check(String[] arr){
        String current;
        String previous;
        boolean flag = true;
        previous = arr[0];
        for(int i=1;i<arr.length;i++){
            current = arr[i];
            if(current.equals(previous)){
                flag=false;
                break;
            }
            previous = arr[i];
        }
        if(flag){
            count++;
        }
    }
    static void swap(String[] arr, int i, int depth){
        String temp= arr[i];
        arr[i]=arr[depth];
        arr[depth]=temp;
    }
    static int fact(int num){
        int sum=1;
        for(int i=1;i<=num;i++){
            sum*=i;
        }
        return sum;
    }
	public static void main(String[] args) {
	    int answer;
        Scanner sc = new Scanner(System.in);
        String str;
        str = sc.nextLine();
        String[] arr = str.split("");
        HashMap<String,Integer>map = new HashMap<>();
        for(int i=0;i<arr.length;i++){
            if(map.containsKey(arr[i])){
                map.put(arr[i], map.get(arr[i])+1);
            }
            else{
                map.put(arr[i],1);
            }
        }
        perm(0,arr);
        int sum=1;
        for(int value: map.values()){
            sum*=fact(value);
        }
        
        answer = count/sum;
        System.out.println(answer);

	}
}