[백준/1342] 행운의 문자열 - JAVA

📌 문제

알고리즘 분류 : 백트래킹
난이도 : 실버1
출처 : 백준 - 행운의 문자열

🦧 문제 풀이 접근

map을 이용해서 각 알파뱃별 갯수를 확인한다.
어떤 알파뱃인지는 이제 필요가 없고 알파뱃별 갯수 data를 ArrayList에 넣는다.
재귀 함수를 통해 중복되지않게 1개씩 줄여가면서 가능한 경우를 파악한다.

💻 code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int sum = 0;
    static ArrayList<Integer> arrayList;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        Map<Character, Integer> map = new HashMap<>();
        for(int i=0;i<line.length();i++) {
            if(map.containsKey(line.charAt(i)))
                map.put(line.charAt(i),map.get(line.charAt(i))+1);
            else
                map.put(line.charAt(i),1);
        }
        arrayList = new ArrayList<>(map.values());
        for(int i=0;i<arrayList.size();i++) {
            arrayList.set(i,arrayList.get(i)-1);
            req(i, 1, line.length());
            arrayList.set(i,arrayList.get(i)+1);
        }
        System.out.println(sum);
    }
    private static void req(int lastIndex, int depth, int maxDepth) {
        if(depth == maxDepth) {
            sum++;
            return;
        }
        for(int i=0;i<arrayList.size();i++) {
            if(arrayList.get(i)>0 && lastIndex!=i) {
                arrayList.set(i,arrayList.get(i)-1);
                req(i,depth+1, maxDepth);
                arrayList.set(i,arrayList.get(i)+1);
            }
        }
    }
}

🥇 결과

🎓 느낀점

Map을 이용해서 갯수 파악을 하고 각 알파뱃별 개수 Data를 사용해 완전 탐색을 돌려 시간을 줄일 수 있었다.