백준 [N1062 - 가르침]

백준 가르침 문제설명

 

 

풀이과정

STEP1. 예외처리

최소 1개이상의 단어를 읽기 위해선 a, n, t, i, c 5개의 글자는 기본으로 가르쳐야합니다.
글자 5개미만이라면 0개의 단어를 읽을 수 있고 알파벳 26개의 글자를 모두가르친다면 N개의 단어를 읽을 수 있습니다.
이를 예외처리해주고 a, n, t, i, c외의 K-5개의 글자로 읽을 수 있는 단어의 개수를 구해봅니다.

 

STEP2. a, n, t, i, c 글자 제외 처리, 알파벳 방문처리

N개의 단어 각각 a, n, t, i, c를 제외해 String[] word배열에 저장합니다.

알파벳을 가르쳤는지 확인하기 위한 boolean[] visited배열을 선언하고 a, n, t, i, c는 가르쳤기에 true처리를 해줍니다.

 

STEP3. K-5개의 글자조합 구하기

가르칠 수 있는 글자조합을 구하는 방법은 2가지입니다.

 

(1) 글자 선택여부를 확인하는 visited배열 사용하기

combination매개변수에는 선택할 글자인덱스(=visited인덱스) alpha, 선택한 글자조합길이 len이 들어갑니다.

(2) 글자 선택여부를 확인하는 비트마스크 사용하기

아래와 같이 비트마스크의 원소 추가연산을 통해 가르친 a, n, t, i, c 표현합니다.

mask = 0;
mask |= 1 << 'a'-'a' ;       // mask =                                  1 
                                                                                (a)

mask |= 1<<'n'-'a';        // mask =            1                      1
                                                        (n)                   (a)

mask |= 1<<'t'-'a';        // mask =  1         1                     1 
                                              (t)      (n)                    (a)

mask |= 1<<'i'-'a';         // mask=  1          1     1             1
                                              (t)       (n)      (i)           (a)

mask |= 1<<'c'-'a';         // mask = 1          1     1        1   1
                                              (t)        (n)   (i)      (c)    (a)

combination매개변수에는 글자조합길이 len, 비트마스크 시프트연산에사용될 start, 글자선택여부확인할 mask가 들어갑니다.

 

선택하지 않은 글자는 선택처리를 하고 다음에 선택할 글자를 찾기위해 재귀에 들어가게 됩니다. len이 k-5가 되면 글자조합이 완성됩니다. 구한 글자조합으로 최대 몇개의 단어를 읽을 수 있는지 max변수를 통해 출력합니다.

 

---

 

소스코드

 

(1) visited배열 사용하기

public class 가르침 {
    private static int N, K;
    private static String[] word;
    private static boolean[] visitied = new boolean[26];
    private static int max = Integer.MIN_VALUE;
    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());
        if(K<5) {
            System.out.println("0");
            return;
        }
        else if(K==26) {
            System.out.println(N);
            return;
        }
        else {
            //a,n,t,i,c 필수로 가르치기에 가르칠 수 있는 K-5개 글자에서 제외
            word= new String[N];
            for (int i = 0; i < N; i++) {
                String str = br.readLine().replaceAll("[a,n,t,i,c]", "");
                word[i] = str;
            }
             visitied['a'-'a'] = true;
             visitied['n'-'a'] = true;
             visitied['t'-'a'] = true;
             visitied['i'-'a'] = true;
             visitied['c'-'a'] = true;
            //k-5개의 글자조합
            combination(0,0);
            System.out.println(max);
        }
        br.close();
    }

    private static void combination(int alpha, int len) {
        if(len==K-5){
            int cnt = 0;
            for(int i=0;i<N;i++){
                boolean read = true;
                for(int j=0;j<word[i].length();j++){
                    if(!visitied[word[i].charAt(j)-'a']){
                        read = false;
                        break;
                    }
                }
                if(read) cnt++;
            }
            max = Math.max(max, cnt);
            return;
        }
        for(int i=alpha;i<26;i++){
            if(!visitied[i]){
                visitied[i] = true;
                combination(i,len+1);
                visitied[i] = false;
            }
        }
    }
}

 

(2) 비트마스크 사용하기

public class 가르침 {
    private static int N, K;
    private static String[] word;
    private static int mask;
    private static int max = Integer.MIN_VALUE;
    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());
        if(K<5) {
            System.out.println("0");
            return;
        }
        else if(K==26) {
            System.out.println(N);
            return;
        }
        else {
            //a,n,t,i,c 필수로 가르치기에 가르칠 수 있는 K-5개 글자에서 제외
            word= new String[N];
            for (int i = 0; i < N; i++) {
                String str = br.readLine().replaceAll("[a,n,t,i,c]", "");
                word[i] = str;
            }
            //k-5개의 글자조합
            mask = 0;
            mask |= 1<<'a'-'a';
            mask |= 1<<'n'-'a';
            mask |= 1<<'t'-'a';
            mask |= 1<<'i'-'a';
            mask |= 1<<'c'-'a';

            combination(0, 1, mask);
            System.out.println(max);
        }
        br.close();
    }


    private static void combination(int len, int start, int mask) {
        if(len==K-5){
            int cnt = 0;
            for(int i=0;i<N;i++){
                boolean read = true;
                for(int j=0;j<word[i].length();j++){
                    if((mask&(1<<word[i].charAt(j)-'a'))==0){
                        read = false;
                        break;
                    }
                }
                if(read) cnt++;
            }
            max = Math.max(max, cnt);
            return;
        }
        for(int i=start;i<26;i++){
            if((mask&(1<<i))!=0) continue;
            combination(len+1, i+1, mask | 1<<i);
        }
    }
}