백준_18119_단어 암기

문제

18119번: 단어 암기

풀이

파이썬을 이용한 풀이는 같은 방식으로 코드를 작성해도 시간초과로 테스트를 통과하지 못했다. 시간을 줄일 수 있는 해결방법을 찾지 못해서 자바로 풀이를 진행하였다.

 

table에는 알파벳의 포함 여부를 기록한다. 단어별로 a부터 z까지 문자의 포함 여부를 기록하여, 단어 하나당 0부터 2**26(67108864)까지의 수를 저장한다. 쿼리의 내용은 비트 연산자를 이용하여 bitmask에 저장한다. table을 순회 하면서 (원래값&bitmask)==원래값이 성립할때 완전히 알고 있는 단어의 개수 ans를 1씩 늘린다.

 

예를 들어 'apple'이라는 단어에 '1 e' '2 c'라는 쿼리를 순서대로 대입하였을 때 연산의 과정은 아래과 같다.

 

코드

import java.util.Scanner;

public class Main{
     public static void main(String []args){
        Scanner scan = new Scanner(System.in);
        
        int N = scan.nextInt();
        int M = scan.nextInt();
        int[] table = new int[N];
        
        // 알파벳의 포함 여부를 기록
        String word = "";
        for (int i=0;i<N;i++){
            word = scan.next();
            for (int j=0;j<word.length();j++){
                table[i] |= 1<<(word.charAt(j)-'a');
            }
        }
        
        // 쿼리 수행
        int bitmask = -1; // 쿼리 내용 저장
        while (M-->0){
            int cmm = scan.nextInt();
            char alpha = scan.next().charAt(0);
            
            if (cmm==1){
                bitmask &= ~(1<<(alpha-'a'));
            }
            else {
                bitmask |= (1<<(alpha-'a'));
            }
            
            int ans = 0;
            for (int k=0;k<N;k++){
                if (table[k]==(table[k]&bitmask)){
                    ans++;
                }
            }
            System.out.println(ans);
        }
     }
}

알고리즘

• 브루트포스 알고리즘
• 비트마스킹