[JAVA]백준 1062번 가르침

📌문제 링크

---

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

📌문제 설명

---

K개의 알파벳에 대해 백트래킹을 진행하고 알파벳 개수가 K가 되었을때, 몇 개의 단어를 셀 수 있는지 검사해주면 됩니다. a n t i c는 무조건 읽어야 하므로 K값이 5 아래이면 0을 출력합니다.

📌코드

---

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 입력을 받기 위한 BufferedReader
    static int N, K; // N: 단어의 개수, K: 배울 수 있는 글자 개수
    static String[] arr; // 단어를 저장할 배열
    static boolean[] alpha = new boolean[26]; // 알파벳 사용 여부를 저장하는 배열
    static int max = 0; // 최대로 읽을 수 있는 단어 개수를 저장하는 변수

    public static void main(String[] args) throws Exception {
        input(); // 입력 받기
        solve(); // 문제 해결
    }

    public static void input() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); // 단어 개수 입력
        K = Integer.parseInt(st.nextToken()); // 배울 수 있는 글자 개수 입력

        arr = new String[N]; // 단어 배열 초기화

        // 단어 입력 받기
        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            if (str.startsWith("anta") && str.endsWith("tica")) { // 단어의 기본 형식 검사
                arr[i] = str.substring(4, str.length() - 4); // "anta"와 "tica" 부분 제거
            }
        }
        br.close(); // 입력 스트림 닫기
    }

    public static void backTracking(int alphaCnt, int idx) {
        // 배울 수 있는 K개의 글자를 모두 선택한 경우
        if (alphaCnt == K) {
            int cnt = 0; // 읽을 수 있는 단어 개수 카운트
            for (String str : arr) {
                if (str == null) continue; // 단어가 없는 경우 건너뛰기 (NullPointerException 방지)

                boolean flag = true; // 현재 단어를 읽을 수 있는지 여부
                for (int i = 0; i < str.length(); i++) {
                    if (!alpha[str.charAt(i) - 'a']) { // 해당 문자가 배운 알파벳에 없으면 읽을 수 없음
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    cnt++; // 읽을 수 있는 단어 개수 증가
                }
            }
            max = Math.max(max, cnt); // 최댓값 갱신
            return;
        }

        // 백트래킹을 사용하여 글자 선택
        for (int i = 0; i < 26; i++) {
            if (!alpha[i] && i > idx) { // 아직 배우지 않은 알파벳이면서, 이전 알파벳보다 큰 경우에만 선택 (중복 방지)
                alpha[i] = true; // 해당 알파벳 선택
                backTracking(alphaCnt + 1, i); // 재귀 호출하여 다음 글자 선택
                alpha[i] = false; // 백트래킹 (선택 취소)
            }
        }
    }

    public static void solve() {
        // 반드시 배워야 하는 글자 ('a', 'n', 't', 'i', 'c') 미리 선택
        alpha['a' - 'a'] = true;
        alpha['n' - 'a'] = true;
        alpha['t' - 'a'] = true;
        alpha['i' - 'a'] = true;
        alpha['c' - 'a'] = true;

        K -= 5; // 필수 글자 5개를 배웠으므로 남은 학습 가능 글자 개수 조정

        // 배울 수 있는 글자 개수가 0보다 작다면, 추가로 배울 수 있는 글자가 없으므로 0 출력
        if (K < 0) {
            System.out.println(0);
            return;
        }

        backTracking(0, 0); // 백트래킹 시작
        System.out.println(max); // 결과 출력
    }
}