백준 1062 가르침(조합)

1062번: 가르침

뭔가 카카오 코딩테스트에서 많이 나올법만 문제 유형이였다.

 

K개의 단어를 학습하려고 하고 anti - tica는 무조껀 단어에 존재한다고 하니까 5글자는 무조껀 학습이 되어야하는 상황이다.

 

그렇다면 K<5, K>=5인 경우로 크게 나눠볼 수 있고

 

배워야하는 단어의 수 : X 라고 한다면 

 

X < K-5라면 무조껀 X는 다 배울 수 있기 때문에 주어진 단어를 모두 다 배울 수 있다.

X >= K-5라면, X개 중 K-5개를 뽑아서 check()해봐야하기 때문에 조합이 적용된다.

 

Q) 왜 K-5일까? K개를 학습할 수 있는데 anti - tica때문에 5글자는 무조껀 기본으로 들어가고 K-5개를 추가적으로 학습할 수 있는 선택지가 있기 때문에 총 배울 수 있는 선택지들 중에서 K-5개를 뽑는 조합이 들어가는 것이다.

근데 X < K-5라면 X를 모두 학습하더라도 남기 때문에 모든 단어를 다 배울 수 있다는 뜻이다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

/*
* K개의 글자로만 이루어진 단어만 읽을 수 있음
* 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 될까
*
* anta - tica
* a:3, c:1, i:1, t:2, n:1
*
* 기본적으로 5글자는 알아야 단어를 읽을 수 있는 권한이 생김
* K<5면 그냥 0
* K>=5라면 어떤 단어를 추가했을 때 가장 적절한지 일일히 확인 해보기
*
* substring으로 일일이 단어를 뺄 수 있고 어떤 알파벳이 필요한지 리스트를 뽑아낼 수 있으며
* 총 몇개 중 K-5개를 뽑았을 떄 그때의 최댓값이니까 조합으로 풀면될 듯?
* 
*
* */

public class Main{
    static int res;
    static int N,K;
    static List<Character> list;
    static String[] data;
    static boolean[] alphabet;

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

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

        data = new String[N];
        alphabet = new boolean[26];

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

        list = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            String temp = br.readLine();

            int str_length = temp.length();
            data[i] = temp.substring(4, str_length-4);

            for (int j = 0; j < data[i].length(); j++) {
                if (!alphabet[data[i].charAt(j) - 'a']){
                    list.add(data[i].charAt(j));
                    alphabet[data[i].charAt(j) - 'a'] = true;
                }
            }
        }

        for (int i = 0; i < list.size(); i++) {
            alphabet[list.get(i) - 'a'] = false;
        }

        if (K <5)
            System.out.println(0);
        else{
            res = 0;

//            System.out.println(Arrays.toString(data));
//            System.out.println(list.toString());

            if (list.size() <= K-5)
                res = data.length;

            // 여기서 조합을 한다고 치자
            // r을 골랐다고 했으면 r을 골랐을 때 몇개를 알 수 있는지 check()는 어케함?
            // for data해서 5개말고 고른 알파벳이 있다면 res++
            combi(0, 0, new char[K-5]);

            System.out.println(res);
        }
    }

    public static void combi(int start, int depth, char[] select){
        if (depth == (K-5)){

//            System.out.println(Arrays.toString(data));
//            System.out.println(list.toString());

            // visited = true;
            for (int i = 0; i < select.length; i++) {
                alphabet[select[i] - 'a'] = true;
            }

            int cnt = 0;

            for (int i = 0; i < data.length; i++) {
                boolean flag = true;
                for (int j = 0; j < data[i].length(); j++) {
                    if (!alphabet[data[i].charAt(j) - 'a']) {
                        flag = false;
                        break;
                    }
                }

                if (flag)
                    cnt++;
            }

            res = Math.max(res,cnt);

            // visited = false;
            for (int i = 0; i < select.length; i++) {
                alphabet[select[i] - 'a'] = false;
            }
            return ;
        }

        for (int i = start; i < list.size(); i++) {
            select[depth] = list.get(i);
            combi(i+1,depth+1,select);
        }
    }
}