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

문제

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

---

풀이(15분)

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

public class Main {

    static Set<Character> alphabet = new HashSet<>(); // 사용될 알파벳 집합
    static int[] alphabetCount = new int[26]; // 알파벳의 개수를 체크할 배열
    static int count, stringLength; // 정답 개수와 문장의 길이

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        String s = br.readLine();
        stringLength = s.length();

        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            alphabet.add(c); // 집합에 추가
            alphabetCount[c - 'a']++; // 배열에 카운트 + 1
        }

        for(char c : alphabet){
            dfs(c, 1);
        }

        System.out.println(count);
    }

    static void dfs(char lastAlphabet, int length){
        if(length == stringLength){
            count++;
            return;
        }

        alphabetCount[lastAlphabet - 'a']--;
        for(char c : alphabet){
            if(c != lastAlphabet){
                if(alphabetCount[c - 'a'] != 0){
                    dfs(c, length+1); // dfs 깊이 1 추가
                }
            }
        }
        alphabetCount[lastAlphabet - 'a']++;
    }
}

---

문제 풀이 전략

 

전략 자체는 단순하다. 길이가 10인 짧은 문자열을 대상으로 하는 것이기 때문이다.

 

1. 알파벳의 개수와 종류를 체크한다.

2. 알파벳을 하나 선택한다.

3. 사용 가능한 알파벳의 개수에서 뺀다.

4. 이 전 알파벳과 다르게 사용할 수 있는 게 있다면 dfs를 반복한다.

5. 최종적으로 길이가 문자열과 같아졌다면 종료하고 정답을 + 1 한다.

6. 감소한 알파벳을 증가시킨다.