[백준] 1342번 행운의 문자열(java)

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

1342번: 행운의 문자열

DFS를 사용하여 풀 수 있다.

 

핵심

사용할 알파벳이 있느냐, 이전 알파벳이 현재 알파벳과 같으냐 이것을 정의하고 풀 수 있다.

이러한 방법을 사용하면 같은 알파벳이지만, 배열위치가 다른 것도 1번만 확인하게 된다.

ex) aba' == a'ba

 

정답 코드

import java.util.Scanner;

public class Main{
    static int[] alphabet = new int[27];
    static int count;
    static int length;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        length = str.length();
        for (int i = 0; i < str.length(); i++)alphabet[str.charAt(i)-'a']++;

        dfs(0,' ');
        System.out.println(count);
    }

    public static void dfs(int index,char pre){
        if (index==length){
            count++;
            return;
        }

        for (int i = 0; i < 27; i++){
            if (alphabet[i]==0)continue;

            if (pre != (char) (i+'a')){
                alphabet[i]--;
                dfs(index+1, (char)(i+'a'));
                alphabet[i]++;
            }

        }
    }
}

해설

문자열을 입력받으면 알파벳의 개수를 기록한다. 알파벳은 26개이다.

이전값과 다른 값일 경우에만 index를 증가시킨다. 

주어진 문자열의 크기와 같아지면 결괏값을 1 올려준다.

 

 

배운 점

처음에는 각각 배열에 넣고, 완전탐색을 사용하였다. 그러다 보니 중복된 a'ba, aba'를 구분하는 일이 쉽지 않았다.

하지만 위와 같은 방법을 사용하니 중복을 없앨 수 있었고, 더 효율적으로 풀 수 있었다.