문제

가르침

풀이

확실히 실버 문제들 보다는 더 많은 생각을 해야 풀수 있는 문제였다.
알파벳을 k개 외워야 하는데 a,n,t,i,c 는 필수로 알아야 단어를 한개라도 읽을수 있기 때문에 5개는 읽을수 있는 것을 전재로 해야한다. 알파벳 배열을 두고 인덱스별로 읽을 수 있는 것은 true로 변경해야 한다

		if (k >= 5) {
            arr = new String[n];
            for (int i = 0; i < n; i++) {
                arr[i] = sc.next();
            }
            alphabet[0] = true;
            alphabet['n' - 'a'] = true;
            alphabet['t' - 'a'] = true;
            alphabet['i' - 'a'] = true;
            alphabet['c' - 'a'] = true;
            k -= 5;
            dfs(0, 0);
        }

읽을 수 있는 단어들은 알파벳을 전부 알아야 알수 있는데, 알파벳을 dfs로 안다고 생각하고 경우의 수를 전부 방문하면 되는 것이다.

	private static void dfs(int depth, int index) {
        if (depth == k) {
            answer = Math.max(answer, check());
        }

        for (int i = index; i < 26; i++) {
            if (alphabet[i]) continue;
            alphabet[i] = true;
            dfs(depth + 1, i);
            alphabet[i] = false;
        }
    }

    private static int check() {
        int result = 0;
        for (int i = 0; i < arr.length; i++) {
            String a = arr[i];
            boolean check = true;
            for (int j = 0; j < a.length(); j++) {
                if (!alphabet[a.charAt(j) - 'a']) {
                    check = false;
                    break;
                }
            }
            if (check) {
                result++;
            }
        }
        return result;
    }

전체 코드

전체 코드