BOJ - 개구쟁이 준식이(17480)

문제(링크)

범위가 모두 15이하이기 때문에 재귀호출을 이용한 완전 탐색으로 풀 수 있습니다.
먼저 준식이가 말한 알파벳에 맞게 전체 단어에서 sub 단어를 분리해줍니다. -> isCorrect()
시작 인덱스(s) 와 종료 인덱스(e) 가 주어지면 해당 위치만 역순으로 바꾸는 swap() 함수를 구현합니다.
그리고 재귀 함수를 돌면서 앞쪽을 바꾼 경우(front), 뒤쪽을 바꾼 경우(back)에 따라 인덱스를 조절해가며 재귀 호출해줍니다.
역순으로 바꿀 단어가 홀수인 경우엔 시작 인덱스(s)를 1 증가시켜 한번 더 재귀 호출합니다.

중복 확인은 해쉬맵을 이용합니다.

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

public class Main {

    public static int N, sum;
    public static String str;
    public static HashMap<String, Boolean> hm = new HashMap<>();
    public static int[] alpha = new int[26];
    public static void main(String[] argc) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        sum = 0;

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N ; i++) {
            sum += alpha[st.nextToken().charAt(0) - 'a'] = Integer.parseInt(st.nextToken());
        }

        str = br.readLine();

        for (int i = 0; i <= str.length() - sum ; i++) {
            StringBuilder sub = new StringBuilder().append(str.substring(i, i + sum));
            if(isCorrect(sub.toString())){
                half(sub, 0, sub.length());
            }
        }
        System.out.println(hm.size());
    }
    public static boolean isCorrect(String s){
        int[] check = new int[26];
        for (int i = 0; i < 26 ; i++) {
            check[i] = alpha[i];
        }
        for (int i = 0; i < s.length() ; i++) {
            if(--check[s.charAt(i) - 'a'] < 0)
                return false;
        }
        return true;
    }
    public static void half(StringBuilder str, int s, int e){
        if(e == s + 1 || e == s + 2) {
            if(!hm.containsKey(str.toString()))
                //이미 들어가있는 문자열이 아니라면
                hm.put(str.toString(), true);
            return;
        }

        StringBuilder front = swap(str, s, (s + e) / 2);
        StringBuilder back = swap(str, (s + e) / 2, e);
        //front = 앞쪽이 반전된 문자열
        //back = 뒤쪽이 반전된 문자열

        half(front, (s + e) / 2, e);
        half(back, s, (s + e) / 2);

        if((s + e) % 2 != 0) {
            //홀수인 경우 시작 길이를 1 늘려 경우를 추가해줌.
            front = swap(str, s, (s + e) / 2 + 1);
            back = swap(str, (s + e) / 2 + 1, e);

            half(front, (s + e) / 2 + 1, e);
            half(back, s, (s + e) / 2 + 1);
        }
    }
    public static StringBuilder swap(StringBuilder str, int s, int e){
        //s 와 e 사이의 문자열을 반전시키는 함수
        StringBuilder ret = new StringBuilder();

        ret.append(str.substring(0, s)).append(new StringBuilder().append(str.substring(s, e)).reverse());
        if(e < str.length())
            ret.append(str.substring(e, str.length()));
        return ret;
    }
}