[JAVA] 백준 가르침 1062

www.acmicpc.net/problem/1062

1062번: 가르침

 

비트마스크를 이용해 풀어봤다.

 

중요한 점은 영어단어를 굳이 String 이나 char[] 로 표현하지 않아도 된다는 점이다. 

 

예를 들어 "apple" 이라는 단어가 있다고 할 때 여기서 'a','p','l','e' 4가지의 알파벳을 사용했다는 것이 중요하다.

 

따라서 "apple" 이나 "apppple" 이나 "aaaaaple" 이나 모두  'a','p','l','e' 4가지의 알파벳을 사용했다. 이를 유용하게 표현해주는 것이 비트마스크다.

 

[9]	[8]	[7]	[6]	[5]	[4]	[3]	[2]	[1]	[0]
1	0	0	0	1	0	0	1	0	1

 

0번 부터 9번까지 해당하는 알파벳이 a ~ j 이며 위와 같이 비트마스크가 있다면 a,c,f,j 알파벳을 쓴 단어임을 알 수 있다.

 

 

문제풀이)

 

a,n,t,i,c 를 제외한 21개의 알파벳 중에서 k-5개를 고른 것을 mask라고 할때,  어떤 단어의 모든 알파벳이 마스크에 해당하게 된다면 그 단어는 읽을 수 있다. 마스크에 해당하는지 안하는지 확인하려면 부분집합여부를 파악하면 되는데 자세한 내용은 아래를 참조한다.

onejunu.tistory.com/63?category=882329

[JAVA] 비트 연산자를 이용하여 조합 & 부분집합 & 부분집합 여부파악

 

import java.util.*;

class Main{
    static int n,k;
    static List<Integer> words = new ArrayList<>();
    static int answer = 0;
    static boolean[] alphaBool;


    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        k = sc.nextInt();
        k-=5;
        for(int i=0;i<n;i++){
            int word = 0;
            char[] tp = sc.next().toCharArray();
            for(char c : tp){
                if(anticCheck(c)) continue;
                else{
                    if(c=='b'){
                        word |= (1<<(c-'a'-1));
                    }
                    else if(c <= 'i'){
                        word |= (1<<(c-'a'-2));
                    }
                    else if(c <= 'n')
                    {
                        word |= (1<<(c-'a'-3));
                    }
                    else if(c <= 't'){
                        word |= (1<<(c-'a'-4));
                    }
                    else{
                        word |= (1<<(c-'a'-5));
                    }
                }
            }
            words.add(word);
        }
        if(k<0){
            System.out.println(answer);
            return;
        }

        for(int i =0 ;i<1<<21;i++){
            int cnt = 0;
            for(int j=0;j<21;j++){
                if((i&(1<<j)) > 0){
                    cnt++;
                }
            }

            if(cnt == k){
                alphaBool = new boolean[21];
                for(int j=0;j<21;j++){
                    if((i&(1<<j)) > 0){
                        alphaBool[j] = true;
                    }
                }
                int mask =0;
                for(int j=0;j<21;j++){
                    if(alphaBool[j]){
                        mask |= (1<<j);
                    }
                }
                check(mask);
            }
        }
        System.out.println(answer);
    }

    static boolean anticCheck(char c){
        if(c=='a' || c=='n' || c=='t' || c=='i' || c=='c') return true;
        return false;
    }

    static void check(int mask){
        int cnt = 0;
        for(int word : words){
            if((word & mask) == word){
                cnt++;
            }
        }
        answer = answer < cnt ?cnt : answer;
    }
}