[백준, Java] 1062번 : 가르침

🔗 문제 링크

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

😮 문제 해결 방법

문제에서 남극 단어의 시작과 끝은 anta, tica로 끝난다고 했기 때문에 a,n,t,i,c는 반드시 배워야 하는 글자이다.

a,n,t,i,c를 포함해 남은 알파벳 중 k개를 조합한다.

조합한 알파벳을 남극 단어마다 해당 알파벳을 모두 포함하는지 판단하면서 배울 수 있는 단어를 체크한 후 현재 까지 최대로 배울 수 있는 단어 개수와 현재 배울 수 있는 단어 개수를 비교해서 갱신한다.

1. a,n,t,i,c는 반드시 배워야 하는 글자이므로 K가 5보다 작다면 남극 단어를 배울 수 없기 때문에 0을 리턴한다.
2. K가 5보다 크다면 이미 5개를 배웠기 때문에 a,n,t,i,c를 제외한 (K - 5)개의 글자를 백트래킹과 조합을 이용해 추가로 체크한다.
   1. teachingAlphabet이 true 라면 알파벳을 배운 상태이다.
3. 알파벳을 모두 배웠다면, 남극 단어에 포함되어 있는지 판단한다.
4. 현재 알파벳 조합에서 몇개의 남극단어를 배울 수 있는지 체크한 후 지금까지 최대로 배운 단어개수와 비교해 최대값을 갱신한다.

🚩 Java 코드

package com.algorithm.Baekjoon;

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

public class Main_1062_가르침 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        String[] words = new String[N];
        for (int loop = 0; loop < N; loop++) {
            words[loop] = br.readLine();
        }

        int rst = teachAnticWord(K, words);
        System.out.println(rst);

        br.close();
    }

    private static int count;
    private static int teachAnticWord(int K, String[] words) {
        /**
         * 1. a,n,t,i,c는 무조건 배워야하는 글자이므로 K개가 5개 이상이면 5개 빼고 남은 글자로 조합 만들기
         * 2. 만들어진 글자 조합으로 모든 단어에 포함되는 글자인지 탐색 -> 하나라도 포함이 안된 경우 다음 단어로
         * 3. 글자 조합 별 최고로 가르칠 수 있는 단어 개수 갱신
         */
        // a,n,t,i,c를 못배우는 경우 0개
        if(K < 5) return 0;

        count = 0;
        boolean[] teachingAlphabet = new boolean[26];       // 가르칠 알파벳 체크 배열
        // a,n,t,i,c는 무조건 배워야하므로 true
        teachingAlphabet[0] = teachingAlphabet[2] = teachingAlphabet[8] = teachingAlphabet[13] = teachingAlphabet[19] = true;

        teachLetter(0,0, K - 5, words, teachingAlphabet);

        return count;
    }

    // start : 시작 인덱스, letterCount : 배운 글자 개수, finishCount :  배울 글자 개수(a,n,t,i,c 제외)
    private static void teachLetter(int start, int letterCount, int finishCount, String[] words, boolean[] teachingAlphabet) {
        if(letterCount == finishCount) {
            // 2. 만들어진 글자 조합으로 모든 단어에 포함되는 글자인지 탐색 -> 하나라도 포함이 안된 경우 다음 단어로
            int teachingCount = 0;
            for (String word : words) {
                boolean teach = true;
                for (char letter : word.toCharArray()) {
                    if(!teachingAlphabet[letter-97]) {   // 아스키코드 97 : a
                        teach = false;
                        break;
                    }
                }
                if(teach) teachingCount++;
            }

            // 3. 글자 조합 별 최고로 가르칠 수 있는 단어 개수 갱신
            count = Math.max(count, teachingCount);
            return;
        }

        // 배울 수 있는 알파벳 조합 만들기
        for(int alpha = start; alpha < 26; alpha++) {
            if(!teachingAlphabet[alpha]) {
                teachingAlphabet[alpha] = true;
                teachLetter(alpha +1, letterCount+1, finishCount, words, teachingAlphabet);
                teachingAlphabet[alpha] = false;
            }
        }
    }
}