가르침

📍 문제 설명

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

1062번: 가르침

 

💡 접근

조합 문제. 단어의 시작과 끝은 무조건 'anta', 'tica'로 끝나기때문에 최소 5글자를 배워야 한다.

모든 단어에 대해서 확인하는 것은 메모리 낭비가 될 수 있으므로 5글자를 제외한 단어만 본다.

해당 단어들을 제외한 단어들로 조합을 돌려서 읽을 수 있는 단어인지 확인하면된다.

 

👩‍💻 코드

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

public class Main {
    static int n, m, v, e, k, r, answer, cnt, max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
    static char[] arr;// dx = {1,0,-1,0}, dy = {0,-1,0,1};
    static long[] dp;
    static int[][] board;
    static boolean[] visited;
    static ArrayList<String> list;
    static TreeSet<Character> set;
    static StringBuilder sb;
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        Main T = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        //단어를 읽으려면 최소 5개의 글자를 가르쳐야한다.
        if(k < 5) {
            System.out.println(0);
            System.exit(0);
        }
        list = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            sb = new StringBuilder();
            st = new StringTokenizer(br.readLine());
            set = new TreeSet<>();
            char[] c = st.nextToken().toCharArray();
            for(int j = 0; j < c.length; j++) {
                if(c[j] != 'a' && c[j] != 'n' && c[j] != 't' && c[j] != 'i' && c[j] != 'c') {
                    set.add(c[j]);
                }
            }
            Iterator<Character> iter = set.iterator();
            while(iter.hasNext()) {
                sb.append(iter.next());
            }
            list.add(sb.toString());
        }
        arr = new char[k-5];

        T.solution(0,0);
        System.out.println(max);
    }

    private void solution(int L, int s) {
        if(L == k-5) {
            answer = 0;
            //읽어야하는 단어들 탐색 [by, x, d, e, f, g, h, j, k]
            readWord();
            max = Math.max(max, answer);
            return;
        }
        else {
            for (int i = s; i < 26; i++) {
                arr[L] = (char) ('a' + i);
                if(arr[L] != 'a' && arr[L] != 'n' && arr[L] != 't' && arr[L] != 'i' && arr[L] != 'c') {
                    solution(L + 1, i + 1);
                }
            }
        }
    }

    private void readWord() {
        for(int i = 0; i < list.size(); i++) {
            boolean flag = true;
            //뽑은 글자 수 보다 리스트에 담긴 글자가 더 많으면 읽을 수 없어
            if(list.get(i).length() > arr.length) continue;

            //가르친 단어들로 읽어야하는 단어들 몇개 읽을 수 있는지 확인(arr) [b, d, e]
            int len = 0;
            int len2 = 0;

            while(len < list.get(i).length() && len2 < arr.length) {
                //읽을 수 있는 글자면 읽고 둘다 증가시켜줘
                if(list.get(i).charAt(len) == arr[len2]) {
                    len++;
                    len2++;
                }
                //같지 않으면 다음 가르친 단어를 확인해
                else {
                    len2++;
                }
            }
            //len이 length면 읽은것
            if(len == list.get(i).length()) {
                answer++;
            }
        }
    }


}