[BOJ] 백준 [1062] 가르침 JAVA

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

1062번: 가르침

📝문제

📝풀이

단순히 문자열 완전탐색으로 풀 수 있었다.
우선, anta tica 부터 5개의 알파벳을 차지하고 시작하므로 k>5 인경우에만 진행해야 한다.

pattern matching 함수를 사용하여 만약, 해당 패턴의 단어가 있으면 anta tica를 제외한 부분만 
문자열 리스트에 추가한다.

알파벳 방문 체크 배열 visit 을 하나씩 체크하다가 k 개의 갯수가 되었다면 문자열 리스트를 순회하여 모두 읽을 수 있는지 체크

import java.util.*;
import java.io.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import java.util.stream.*;

import static java.util.Arrays.stream;

public class Main {


    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int n,k;
    static int ans=0;
    static String[] words;
    static boolean[] visit = new boolean[26];
    public static void main(String[] args) throws IOException {
        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        k = Integer.parseInt(input[1]);

        visit['a'-'a']=true;
        visit['n'-'a']=true;
        visit['t'-'a']=true;
        visit['i'-'a']=true;
        visit['c'-'a']=true;

        if(k<5){
            System.out.println(ans);
            return;
        }
        words = new String[n];
        k = k-5;
        Pattern pattern = Pattern.compile("anta(.*)tica");
        for(int i=0;i<n;i++){
            Matcher matcher = pattern.matcher(br.readLine());
            if(matcher.find())
                words[i] = matcher.group(1);
        }

        dfs(0,0);
        System.out.println(ans);
    }

    static void dfs(int cur,int len){

        if(len == k){
            int cnt = 0;

            for(int i=0;i<n;i++){
                boolean read = true;

                for(int j = 0; j< words[i].length(); j++){

                    if (!visit[words[i].charAt(j) - 'a']) {
                        read = false;
                        break;
                    }
                }
                if(read)
                    cnt++;
            }

            ans = Math.max(ans,cnt);
            return;
        }

        for(int i=cur;i<26;i++){
            if(!visit[i]){
                visit[i]=true;
                dfs(i,len+1);
                visit[i]=false;
            }
        }
    }
}