101. 단어 암기 (백준 18119) [JAVA]

문제

문제 링크 : https://www.acmicpc.net/problem/18119

18119번: 단어 암기

문제

준석이는 영어 단어를 외우려고 한다. 사전에는 N가지 단어가 적혀 있다. 모든 단어는 소문자이다. 단어 안에 있는 모든 알파벳을 알 때, 그 단어를 완전히 안다고 한다.

다음과 같은 쿼리들이 주어진다.

• 1 x : 알파벳 x를 잊는다.
• 2 x : 알파벳 x를 기억해 낸다.

처음에 모든 알파벳을 기억하는 상태고, 모음은 완벽하게 외웠기 때문에 절대 잊지 않는다.

각 쿼리마다 완전히 알고 있는 단어의 개수를 출력하여라.

첫 번째 줄에는 집의 가로 길이 N과 세로 길이 M이 입력된다. (3 ≤ N, M ≤ 50)

두 번째 줄부터는 집의 구조가 예제 입력과 같이 주어진다.

비어있는 곳은 '.'로 벽은 '#'로 입력된다. 경재 씨의 현재 위치는 S, 나가는 문의 위치는 E, 챙겨야 하는 물건은 종류에 상관없이 X로 입력된다.

챙겨야 하는 물건은 최대 5개까지 있을 수 있다. 집은 언제나 벽으로 둘러싸여 있고, 나가는 문은 언제나 하나이다.

입력

첫 번째 줄에는 정수 N (1 ≤ N ≤ 104)과 M (1 ≤ M ≤ 5×104)이 주어진다.

다음 N개의 줄에는 문자열이 하나씩 주어진다. 문자열의 길이는 103을 넘지 않는다.

다음 M개의 줄에는 정수 o와 문자 x가 한 줄씩 주어진다. o는 1, 2중 하나이고, x는 알파벳 소문자이다.

o가 1이면 x를 잊는다는 뜻이고, o가 2면 x를 기억해낸다는 뜻이다. o가 1일 때는 x를 기억하고 있었음이 보장되고, o가 2일 때는 x를 잊고 있었음이 보장된다.

출력

각 쿼리마다 정수 하나를 출력한다.

풀이

$10^4$ 개의 단어를 $5\times 10^4$ 번 체크해야 하기 때문에 단어를 String이나 Char로 처리하려면 시간초과에 걸린다.

그래서 생각한 풀이법은 각 단어의 알파벳을 int형으로 전환하여 단어를 정수화 시킨 뒤

내가 외우고 있는 알파벳에다 and 연산을 통해 정확히 알파벳들을 외우고 있는지 체크하는 방법이다.

단어의 알파벳을 정수화 시킬 때에는 비트이동 뒤 or 연산을 사용하여 중복처리를 하였고

알파벳에서 다시 기억하는것은 or 연산으로 처리해주었다.

알파벳을 잊는 과정은 모든 알파벳을 외우고 있다는 상태에서, 해당 알파벳을 빼서 거기에 해당하는 비트만 0으로 바꾸고 외우고 있는 알파벳과 &연산을 하여 적용시켰다.

어차피 x를 잊을때는 x를 기억하고 있었음이 보장되기 때문에 그냥 - 연산을 해도 되지만, 이상하게도 이렇게 한 방식이 가장 시간이 빠르게 나왔다.

코드

import java.io.*;
import java.util.*;

public class Main {

    static int N;
    static int M;
    static long[] words;
    static long defaultAlphabet = (1<<26)-1;
    static long alphabet;
    static ArrayList<Integer> answers = new ArrayList<>();

    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());
        M = Integer.parseInt(st.nextToken());

        words = new long[N];

        for(int i=0; i<N; i++){
            words[i] = exChangeBit(br.readLine());
        }

        //비트 다 1로
        alphabet = defaultAlphabet;

        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            //forget
            if(Integer.parseInt(st.nextToken()) == 1){
                alphabet = alphabet & defaultAlphabet - (1 << st.nextToken().charAt(0)-97);
            }
            //remember
            else{
                alphabet = alphabet | (1 << st.nextToken().charAt(0)-97);
            }
            checkWord();
        }

        for(int ans : answers){
            System.out.println(ans);
        }
    }

    public static long exChangeBit(String s){
        long word = 0;
        for(char c : s.toCharArray()){ //소문자는 96부터
            word = word | (1 << (c-97));
        }
        return word;
    }

    public static void checkWord(){
        int answer = 0;
        for(long word : words){
            if((alphabet & word) == word){
                answer++;
            }
        }
        answers.add(answer);
    }
}

결과