[알고리즘] 백준 - 가르침

백준 - 가르침

내 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;


public class baekjoon_1062 {
    static int N, K;
    static int maxAns = 0;
    static boolean[] alphaArr = new boolean[26];
    static String[] testWords;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");
        N = Integer.parseInt(inputs[0]);
        K = Integer.parseInt(inputs[1]);
        if (K < 5) {
            System.out.println(0);
            return;
        }
        testWords = new String[N];
        for (int n = 0; n < N; n++) {
            testWords[n] = br.readLine();
        }
        // a n t i c 는 무조건 읽을 수 있어야한다 anta tica는 필수기 때문에
        alphaArr[(int)'a' - (int)'a'] = true;
        alphaArr[(int)'n' - (int)'a'] = true;
        alphaArr[(int)'t' - (int)'a'] = true;
        alphaArr[(int)'i' - (int)'a'] = true;
        alphaArr[(int)'c' - (int)'a'] = true;

        backTracking(0, 0, K-5);
        System.out.println(maxAns);
    }

    private static void backTracking(int curPos, int curCount, int maxCount) {

        if (curPos >= 26 && curCount < maxCount) {
            return;
        }
        if (curCount == maxCount) {
            int readableCount = 0;
            for (int n = 0; n < N; n++) {
                if (checkReadable(testWords[n])) {
                    readableCount++;
                }
            }
            maxAns = Math.max(readableCount, maxAns);
            return;
        }

        if (alphaArr[curPos] == false) {
            alphaArr[curPos] = true;
            backTracking(curPos+1, curCount+1, maxCount);
            alphaArr[curPos] = false;
        }
        backTracking(curPos+1, curCount, maxCount);
    }

    private static boolean checkReadable(String testWord) {
        for (int i = 4; i < testWord.length() - 4; i++) {
            if (!alphaArr[(int) testWord.charAt(i) - (int) 'a']) {
                return false;
            }
        }
        return true;
    }
}

백트랙킹 중에서도 좀 더 세밀하게 문제 조건을 따져야하는 문제다. 처음에 꼭 배워야 하는 알파벳 다섯개가 주어진다. 그래서 K가 4개이하면 바로 종료 시켜야한다. 또한 문자열 검증을 할때도 앞뒤 4개씩 자르고 하면 속도가 좀 더 빠르다.