[백준] 18119 단어 암기

※ 사용언어 : 자바 ※

 

▼ 문제 링크 ▼

https://www.acmicpc.net/problem/18119

 

---

 

문제 접근

1. 완전 탐색을 이용, 각 쿼리가 이루어질 때마다 각 단어의 알파벳을 다 기억하고 있는지 검사하면 시간 초과로 문제를 풀 수 없습니다. 그러므로 비트마스킹을 이용해 알고리즘 수행 시간을 감소시켜야 합니다.

2. 비트마스킹이란 정수의 이진수 표현을 자료구조로 이용하는 방식입니다.

3. 접근

1) 준석에는 처음에 모든 알파벳을 기억하고 있는 상태입니다. 모든 알파벳을 기억하는 변수(allAlphabet)를 하나 만들어줍니다. 알파벳은 총 26개로 0부터 시작한단 가정 아래 25개의 숫자열이 탄생하게 됩니다. 초기에는 전부 기억하고 있으니 아래 첨부된 표처럼 26개의 1이 나열된 숫자열이 생깁니다.

1이 26개가 나열된 숫자열을 만드는 방법은 간단합니다. 1을 27번 Left Shift로 처리 해준 다음 1을 빼면 됩니다. 왜 이렇게 되는지 4개의 1이 나열된 숫자를 통해 알아보도록 하겠습니다.

일단 1을 5번 Left Shift 를 하게 되면 10000(2) = 16입니다. 16 - 1은 15이고, 15를 2진수로 풀면 1111(2)입니다. 이렇게 4개의 1이 나열된 숫자열이 만들어졌습니다.

 

2) 커맨드에 따라 알파벳을 기억하는지 까먹는지 결정합니다.

① 기억하는 경우 ▶ alphabets |= 1 << ( 기억할 알파벳 -'a')

abcd라는 알파벳만 있으며, b를 현재 준석이가 까먹은 상태라고 가정합시다. 현재 alphabets = 1011(2) 상태입니다.

이번 쿼리문을 통해 준석이가 b를 기억하는 경우, 1 << ('b' -'a')이고, 아스키코드값에 의해 b는 98, a는 97이므로 'b'-'a' = 1이 됩니다. 1을 1만큼 Left shift를 할 경우 10(2)이 되면서 다음과 같아집니다.

해당 연산을 OR로 취하면? 

1111(2)이 되면서 모든 a, b, c, d 모두 기억하는 상태가 됩니다.

 

② 기억하지 못하는 경우 ▶ alphabets &= ~(1 << ( 기억할 알파벳 -'a'))

abcd라는 알파벳만 있고, 현재 준석이는 abcd를 모두 기억하고 있습니다. 

쿼리문으로 인해 c를 까먹었다고 생각해봅시다. 1 << ('c'-'a')이고 아스키코드 값에 의해 c는 99, a는 97 이므로 'c'-'a'는 2입니다. 1을 2만큼 Left shift 시킨 뒤 ~ (not)을 취하면 다음과 같아집니다.

기존 상태와 연산 결과로 나온 값을 And 연산을 취하면?

1011(2)이 되면서 c를 까먹게 됩니다.

 

3) 쿼리 수행 이후 사전에 있는 단어를 기억하고 있는지 없는지 확인합니다.

① 사전에 기록된 단어를 비트 마스킹으로 표현해줍니다. 예를 들어 사전에 "ac" 라는 단어가 있다면, "ac" 를 비트마스킹으로 표현하면 다음과 같습니다.

만약 준석이가 기억하고 있는 상태가 다음과 같다고 생각해봅시다.

해당 상태에 And 연산을 취하면,

And 연산된 값과 "ac" 연산된 값을 보면 같다는 걸 알 수 있습니다. 이를 통해 기억하고 있는 상태 & 단어 == 단어인 경우 해당 단어를 기억하고 있다는 걸 알 수 있습니다.

 

 

---

 

문제풀이(With Java)

package BackJoon;

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

public class Main {
    public static void main(String[] args) 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());

        String[] wordList = new String[N];

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

        // 알파벳을 모두 알고 있다고 가정
        int allAlphabet = ( 1 << 27 ) -1;

        int[] binWord = new int [N];
        for (int i = 0; i < N; i++) {
            for (char c: wordList[i].toCharArray()) {
                // 사전에 등록된 알파벳 값을 비트마스킹 화
                binWord[i] |= ( 1 << c-'a' );
            }
        }

        for (int i = 0; i < M; i++) {
            StringTokenizer command = new StringTokenizer(br.readLine());
            int number = Integer.parseInt(command.nextToken());
            char alphabet = command.nextToken().charAt(0);
			
            // 알파벳을 잊는 경우
            if (number == 1){
                allAlphabet &= ~( 1 << alphabet-'a');
            }
            // 알파벳을 기억하는 경우
            else {
                allAlphabet |= ( 1 << alphabet-'a');
            }

            int knowCount = 0;
            for (int j = 0; j < N; j++) {
                if ((allAlphabet & binWord[j]) == binWord[j]){
                    knowCount++;
                }
            }
            System.out.println(knowCount);
        }
    }
}