[백준] 1062번 : 가르침 - 자바(JAVA)

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

1062번: 가르침

 

문제 해석

학생들은 K개의 글자로만 이루어진 단어만을 읽을 수 있습니다.

어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 될까요?

 

남극 언어의 모든 단어는 "anta"로 시작하고 "tica"로 끝납니다.

 

문제 풀이 전 설계

항상 a, n , t, i , c라는 5개의 단어는 꼭 필요합니다.

남극 언어의 모든 단어가 anta, tica가 포함되기 때문입니다.

 

subString을 사용해서 실제로 필요한 문자열들만 뽑아놓습니다.

 

이때 어떤 단어 K개를 알려주어야 최대가 될 수 있는지 찾기 위해서는 공통으로 등장하는 단어를 최대한 많이 배워야 합니다.

 

처음에 HashSet을 사용해서 접근하려고 했으나 배열로 풀이하면 훨씬 풀이가 간결해져서 배열로 풀이를 했습니다.

 

코드

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

public class Main_1062_가르침 {
    static int N, K;
    static int result = 0;
    static boolean visit[] = new boolean[26];
    static String[] slicedArr;

    public static void dfs(int start, int count) {
        /*
         * 기저사례: 주어진 K개 만큼 단어를 골랐을 때
         * visit[]에 체크된 단어들과 비교해서 배울 수 있는 단어의 최댓값 구하기.
         */
        if (count == K) {
            int readableCount = 0;
            for (int i = 0; i < slicedArr.length; i++) {
                boolean readable = true;
                for (int j = 0; j < slicedArr[i].length(); j++) {

                    /* K개를 골랐을 때, 고른 단어로 해당 문자열을 읽을 수 있는지 판단 */
                    if (!visit[slicedArr[i].charAt(j) - 'a']) {
                        readable = false;
                        break;
                    }
                }
                if (readable) readableCount++;
            }
            result = Math.max(result, readableCount);
            return;
        }

        // 아직 K개를 배우지 않은 경우 -> 완전 탐색(알파벳 갯수: 26개)
        for (int i = start; i < 26; i++) {
            if (!visit[i]) {
                visit[i] = true;
                dfs(i, count + 1);
                visit[i] = false;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        slicedArr = new String[N];

        // 모든 단어는 "anta-'로 시작하고, "-tica"로 끝남.  필수요소 : a n t i c
        if (K < 5) {
            System.out.println("0");
            return;
        }

        // 알파벳 = 26개이므로 26이면 모두 읽을 수 있음.
        if (K == 26) {
            System.out.println(N);
            return;
        }
        // 접두사 anta 와 접미사 tica 제거.
        for (int i = 0; i < N; i++) {
            String str = bf.readLine();
            slicedArr[i] = str.substring(4, str.length() - 4);
        }

        // a n t i c 5개의 단어는 반드시 포함해야 하므로 -5
        K -= 5;

        // a n t i c -> 방문 체크
        char[] essential = {'a', 'n', 't', 'i', 'c'};
        for (char cur : essential) {
            visit[cur - 'a'] = true;
        }


        // 재귀 + 백트래킹을 통해 최대 읽을 수 있는 단어 찾기
        dfs(0, 0);
        System.out.println(result);

    }

}