백준 1342번) 행운의 문자열 (JAVA)

https://www.acmicpc.net/problem/1342

1342번: 행운의 문자열

#문제

민식이와 준영이는 자기 방에서 문자열을 공부하고 있다. 민식이가 말하길 인접해 있는 모든 문자가 같지 않은 문자열을 행운의 문자열이라고 한다고 한다. 준영이는 문자열 S를 분석하기 시작했다. 준영이는 문자열 S에 나오는 문자를 재배치하면 서로 다른 행운의 문자열이 몇 개 나오는지 궁금해졌다. 만약 원래 문자열 S도 행운의 문자열이라면 그것도 개수에 포함한다.

 

#알고리즘

• 부루트포스 알고리즘

 

#난이도

Silver 1

 

#풀이방법

앞으로 계속 부르트포스 알고리즘만 주구장창 풀 것 같다. 내가 이 유형에 취약하기도 하고  많이 부족하기도 하기 때문이다.  서로 양옆에 자리가 다르기만 하면 되기 때문에 백트래킹을 이용하여 모든 경우의 수를 조사하여 마지막에 

boolean 메소드를 호출하여 양옆이 서로 다른지만 체크하면 될 줄 알았다. (부르트포스 알고리즘이기 때문에..)

하지만 생각과 달리 엄청난 시간이 초과되어 버렸다. 그 이유는 간단하다. 문제에서 제시하는 문자열의 길이는 10이지만

이 모든 경우의 수를 조사한다면  10! = 3,628,800가 나와버려 너무 많은 경우의 수가 나오기 때문이다.

 

하지만 생각해보니 맨 마지막에 행운의 문자열인지 조사할 필요 없이 그냥 백트래킹 과정에서 마지막 문자열과 후보의 문자열이 같은지 다른지 체크한다음 다음 메소드를 호출한다면 모든 경우의 수를 조사할 필요없이 진정한(?) 행운의 문자열이 나오게 된다. 

 

public static void permu(char[] ch,String output,boolean[] visited,int depth,int r){
        
        if(depth == r) {
            num++;
            return;
        }//숫자에 도달했을 경우
        
        for(int i=0; i<r; i++) {
 
            if(!visited[i] && output.charAt(output.length()-1) != ch[i]) {
                
                visited[i] = true;
                output += ch[i];
                
                permu(ch,output,visited,depth+1,r);
                
                output = output.substring(0,output.length()-1);
                visited[i] = false;
                
            }
            
        }
        
    }

 

하지만 이렇게 코드를 짜게 되면 문제가 생겨난다. 만약 문자열이 aaaabbb인 경우 같은 character가 중복되기 때문에

오직 1가지의 행운의 문자열 abababa가 여러개가 나와 문제에서 제시하는 원하는 출력값이 나오지 않는다.

 

그럼 HastSet을 이용하여 중복된 값을 제거하면되지 않나? 라고 생각할 수 있지만 아까 말했듯이 서로다른 문자열 예를 들어 abcdefghij 인 경우 10! = 362800이 Set에 저장되어 메모리 초과가 발생하게 된다.

 

그렇다면 일단 중복된 것 상관없이 위에 처럼 무조건 값이 들어오면 num++을 하고, 나중에 중복된 것을 없애주는 방식으로 가야한다.

 

우리가 중복된 것을 없애주는 방식은 고등학교때 확률과 통계를 생각하면 될 것이다.(필자도 군대 갔다온 후 뇌가 굳어 구글링해서 다시 공부했다는.. ㅜㅜ)  암튼 중복순열을 제거 하는 방식 전체의 경우의 수 / 같은 문자열의 팩토리얼

 

자 예를 들어 aabb라면 전체의 경우의수는 4! 이지만 중복된 character 즉 a가 2개 , b가 2개이므로 각각 2!으로 나누어준다. 따라서 4! / (2!*2!)으로 나누어주면 된다.

 

애초에 divide라는 변수를 선언하여 입력받는 string의 중복된 것들을 각자 for문으로 조사하여 팩토리얼을 이용하여 값을 구한다. 

 

public static int fact(int n) {
        
        int sum = 1;
        
        for(int i = n; i>0; i--) {
            sum *= i;
        }
        
        return sum;
    }//단순히 n!를 반환하는 메소드
    
    public static int div(String str) {
        
        int divide = 1;
        
        ArrayList<Character> s = new ArrayList<>();
        //같은 문자열을 또 다시 조사하는 것을 막기 위한 ArrayList
        
        for(int i=0; i<str.length(); i++) {
            
            if(!s.contains(str.charAt(i))) {
                
                int k = 0;
                
                s.add(str.charAt(i));
                
                for(int j = 0; j<str.length(); j++) {
                    
                    if(str.charAt(i) == str.charAt(j))
                        k++;//같은 것들을 찾음
                }
                
                divide *= fact(k);//divde에 곱해준다.
                
            }
            
        }
        
        return divide;
        
    }//같은 character를 조사하여 팩토리얼 시켜주는 메소드

 

 

 

#전체 코드

import java.util.*;
//4t ,일단 HashSet으로 시간초과 문제는 해결했으나, 메모리초과 문제가 발생한다.
 
 
public class Main {
    
    static int num = 0;
    //lucky_string을 저장할 set
    
    public static int fact(int n) {
        
        int sum = 1;
        
        for(int i = n; i>0; i--) {
            sum *= i;
        }
        
        return sum;
    }//단순히 n!를 반환하는 메소드
    
    public static int div(String str) {
        
        int divide = 1;
        
        ArrayList<Character> s = new ArrayList<>();
        //같은 문자열을 또 다시 조사하는 것을 막기 위한 ArrayList
        
        for(int i=0; i<str.length(); i++) {
            
            if(!s.contains(str.charAt(i))) {
                
                int k = 0;
                
                s.add(str.charAt(i));
                
                for(int j = 0; j<str.length(); j++) {
                    
                    if(str.charAt(i) == str.charAt(j))
                        k++;//같은 것들을 찾음
                }
                
                divide *= fact(k);//divde에 곱해준다.
                
            }
            
        }
        
        return divide;
        
    }//같은 character를 조사하여 팩토리얼 시켜주는 메소드
    
    public static void permu(char[] ch,String output,boolean[] visited,int depth,int r){
        
        if(depth == r) {
            num++;
            return;
        }//숫자에 도달했을 경우
        
        for(int i=0; i<r; i++) {
 
            if(!visited[i] && output.charAt(output.length()-1) != ch[i]) {
                
                visited[i] = true;
                output += ch[i];
                
                permu(ch,output,visited,depth+1,r);
                
                output = output.substring(0,output.length()-1);
                visited[i] = false;
                
            }
            
        }
        
    }
    
 
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        String str = sc.next();
        
        char[] ch = str.toCharArray();
        int length = str.length();
        boolean[] visited = new boolean[length];
        String output = "";
        
        int divide = div(str);
        
        for(int i=0; i<length; i++) {
 
            visited[i] = true;
            output += ch[i];
            
            permu(ch,output,visited,1,length);
            
            output = "";
            visited[i] = false;
            
        }
        
        
        //num에 숫자가 생성됨
        
        
        
        System.out.println(num/divide);
    }
 
}