[백준] 18119번: 단어 암기 - JAVA

🔗 문제 링크

BOJ 18119번: 단어 암기

18119번: 단어 암기

 

📝 풀이 과정

단어가 알고있는 알파벳으로 구성되어 있을 때 아는 단어라고 한다. 따라서 단어를 알파벳을 기준으로 보고 단어에 포함되는 알파벳을 비트마스킹을 통해 처리하려고 하였고, 현재 알고 있는 알파벳도 비트연산을 통해 계속 누적하였다.

 

알파벳은 총 26자리로 이루어져있으며 처음에는 모든 알파벳을 알고있기 때문에 (1 << 27) - 1을 하게되면 26자리의 비트가 모두 1인 상태로 초기화를 해주었다.

 

다음으로 단어를 입력받으며 알파벳 하나씩 |(OR)연산을 통해 해당 알파벳의 위치의 비트를 1로 변경하며 해당 위치의 알파벳을 포함하고 있다는 것을 저장하였다.

 

쿼리를 입력받으며 1이라면 해당 위치의 알파벳의 비트를 0으로 바꿔주기 위해 해당 위치 비트만 켜준 다음 ~(NOT)연산을 통해 뒤집어 해당 위치의 비트만 0으로 변경하여 &(AND)연산을 통해 기억하고 있는 alphabet에서 해당 위치만 꺼주었다.

 

int cnt = 0;
for (int word : words)
  if ((alphabet & word) >= word) cnt++;

이후, for문으로 단어마다 기억하고 있는 알파벳과 &연산을 통해 비교해보고 word에 해당하는 모든 비트가 켜져있다면 &연산을 통해 나온 결과가 word랑 같아지게 되므로 이상일 경우 cnt를 증가시켜 기억하고 있는 단어의 수를 증가하였다.

 

💻 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(), M = sc.nextInt();

        int alphabet = (1 << 27) - 1;
        int[] words = new int[N];
        for (int i = 0; i < N; i++) {
            String word = sc.next();
            for (char ch : word.toCharArray())
                words[i] |= 1 << (ch - 'a');
        }

        for (int i = 0; i < M; i++) {
            int o = sc.nextInt();
            char x = sc.next().charAt(0) - 'a';

            if (o == 1) alphabet &= ~(1 << x);
            else alphabet |= (1 << x);

            int cnt = 0;
            for (int word : words)
                if ((alphabet & word) >= word) cnt++;

            System.out.println(cnt);
        }
    }
}

 

📊 제출 결과