가르침

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

풀이

문자열에 반드시 'anta', 'tica'가 들어가기 때문에 백트래킹으로 알파벳을 선택할 때 {'a', 'n', 't', 'i', 'c'}는 선택하지 않아도 된다.

이를 잘 처리하기 위해 저 문자에 97을 뺀 값을 인덱스로 하는 사이즈가 26인 배열을 만들어 관리를 한다. 위의 문자들은 이미 선택한 것과 같기때문에 1로 만들어준다.

그리고 'a', 'n', 't', 'i', 'c'는 반드시 있어야 하기 때문에 k가 5미만이면 단어를 익힐 수 없기때문에 0을 출력한다.

마찬가지로 k가 26이면 모든 단어를 학습가능해 n을 출력해준다.

그 외에는 백트래킹으로 조합을 만들어 가장 큰 수를 출력해주면 된다.

이 부분에서 많이 어려웠는데 일반적으로 문자열의 인덱싱한 비트와 백트래킹으로 조합한 문자들을 매칭할 때 시간이 많이 걸려 시간초과를 겪었다. 인덱스로 접근하는 것까지는 동일했지만 이것보다 더 줄일 수 있는 방법이 있었다.

이미 앞서 백트래킹을 통해 문자들을 선택했기 때문에 선택한 문자가 지금 학습할 문자열에 있는지 확인만 하면 되는 것이었다. 만약 한 문자라도 문자열에 없다면 바로 이후는 볼 필요가 없기때문에 루프를 빠져나오는 식으로 하니 시간초과 문제를 해결할 수 있었다.

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;

public class Main {
    static int n, m, k;
    static int[] alpha;
    static String[] ins;
    static int max = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        k = Integer.parseInt(input[1]);

        alpha = new int[26];

        char[] def = {'a', 'n', 't', 'i', 'c'};


        for (int i = 0; i < 5; i++) {
            int idx = (int) def[i] - 97;
            alpha[idx] = 1;
        }

        ins = new String[n];

        for (int i = 0; i < n; i++) {
            String s = br.readLine();
            ins[i] = s;
        }

        if (k < 5) {
            bw.write("0\n");
        }
        else if(k == 26) {
            bw.write(n+"\n");
        }
        else {
            backTracking(0,0);
            bw.write(max + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }

    private static void backTracking(int cnt, int start) {
        if (cnt == k - 5) {
            int count = 0;
            for (int i = 0; i < n; i++) {
                boolean isValid = true;
                for(int j = 0;j<ins[i].length();j++) {
                    if(alpha[ins[i].charAt(j) - 97] != 1) {
                        isValid = false;
                        break;
                    }
                }
                if(isValid)
                    count++;
            }
            max = Math.max(max, count);
            return;
        }

        for (int i = start; i<26;i++) {
            if (alpha[i] == 0) {
                alpha[i] = 1;
                backTracking(cnt + 1, i + 1);
                alpha[i] = 0;
            }
        }

    }
}