[Java] 백준 18119. 단어 암기

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

 

 

---

 

 

 

 

문제

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

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

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

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

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

 

 

입력

첫 번째 줄에는 정수 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를 잊고 있었음이 보장된다.

 

 

출력

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

 

 

 

 

---

 

 

풀이

비트마스킹을 사용해 풀 수 있는 문제다.

단어는 소문자로 구성되어 있기 때문에 'a' ~ 'z'까지 26비트로 표현 가능하다. 

예를 들어 a는 0번째 비트, b는 1번째 비트

a  -> (1 << 0) 0001

b  -> (1 << 1) 0010

 

우선 각 단어에 사용된 알파벳에 해당하는 비트를 OR 연산을 통해 하나의 비트마스크로 배열(words)에 저장해둔다.

준석이는 맨 처음에 모든 알파벳을 기억하고 있으므로 잊어버린 알파벳이 없다는 뜻이며, 이 상태를 X = 0으로 표현할 수 있다.

이후 쿼리마다 준석이가 알파벳을 잊거나 기억하게 되면 X를 갱신해주고, 갱신 후 모든 단어를 순회하며 AND 연산을 통해 암기 가능한 단어의 개수를 세주면 된다.

if ((word & X) == 0)

이 조건이 참이라면 해당 단어에 준석이가 잊어버린 알파벳이 포함되지 않았다는 뜻이다.

 

word: 0b0010_0000_0000_0011
X   : 0b0000_0000_0000_0110
------------------------------
&    : 0b0000_0000_0000_0010  → 0이 아님. 준석이가 b, c를 잊었고, 해당 단어에는 b가 포함됨.

 

 

---

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

// https://www.acmicpc.net/problem/18119
public class Main_18119 {
    private static int X; // 준석이가 잊어버린 알파벳 집합
    private static int[] words; // 각 단어가 사용하는 알파벳 집합
    private static int[][] Q; // 쿼리


    public static void main(String[] args) throws IOException {
        init();
        sol();
    }//main


    private static void sol() {
        StringBuilder ans = new StringBuilder();

        // 각 쿼리마다 완전히 알고 있는 단어의 개수를 출력하여라.
        for(int[] q : Q) {
            executeQuery(q);

            int cnt = getCnt();
            ans.append(cnt).append('\n');
        }

        System.out.print(ans);
    }//sol


    private static int getCnt() {
        int cnt = 0; // 알고 있는 단어의 개수

        for(int word : words) {
            // 단어에 있는 알파벳 전부 기억
            if((word & X) == 0) cnt++;
        }

        return cnt;
    }//getCnt


    private static void executeQuery(int[] q) {
        int o = q[0]; // 명령 종류
        int x = q[1]; // 알파벳

        if(o == 1) X |= (1 << x); // o가 1이면 x를 잊는다
        else       X &= ~(1 << x); // o가 2면 x를 기억해낸다

    }//executeQuery


    private static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); // 단어 개수
        int M = Integer.parseInt(st.nextToken()); // 쿼리 개수

        words = new int[N]; // 각 단어가 사용하는 알파벳 집합
        Q = new int[M][2]; // 쿼리

        for(int i=0; i<N; i++) {
            char[] str = br.readLine().toCharArray();
            int word = 0;
            for(char c : str) {
                word |= (1 << (c - 'a'));
            }

            words[i] = word;
        }

        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            // o는 1, 2중 하나이고, x는 알파벳 소문자이다.
            int o = Integer.parseInt(st.nextToken());
            int x = st.nextToken().charAt(0) - 'a';

            Q[i][0] = o;
            Q[i][1] = x;
        }

        br.close();
    }//init


}//class