[BOJ] 백준 18119 단어 암기 - Python/Java

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

18119번: 단어 암기

해설

비트마스킹을 이용해서 풀 수 있는 전형적인 문제입니다.

 

문제에서 주어지는 영어 단어는 모두 소문자로만 주어지기 때문에, 이 문제에서 다뤄야 할 모든 알파벳 경우의 수는 26가지입니다.

 

따라서 모든 알파벳을 다 알고 있는 경우를 11111111111111111111111111, 모든 알파벳을 모두 모르는 경우를 00000000000000000000000000이라고 표현할 수 있죠. 그리고 각 알파벳을 외울 때는 알파벳 인덱스의 값을 1로,  까먹을 때는 0으로 바꿔주면 됩니다.

 

다만, 문제에서 주어지는 매 쿼리마다 단어를 일일이 비교하면 안 되고(시간 복잡도) 주어진 단어를 이미 비트 형태로 만들어 둔 다음 현재 외우고 있는 알파벳들과 & 연산을 통해 모든 값이 존재하면 '단어를 안다'고 결정해주면 됩니다.

 

*비트 연산에 관한 내용은 아래 포스팅에서 정리했습니다.

[Python] 비트마스크(Bit Mask)

 

[풀이 - 파이썬]

import sys
input = sys.stdin.readline

def wordsCount(knowingAlp):
    count = 0
    for w in words:
        # 모든 알파벳을 다 알고 있는 경우에 단어를 안다.
        if knowingAlp & w == w:
            count += 1
    print(count)

n, m = map(int, input().split())
words = [0 for _ in range(n)]
for i in range(n):
    word = input().strip()  # 각 단어를 알파벳 리스트로 받아서
    for w in word:
        words[i] |= 1 << ord(w) - 97  # 각 알파벳의 위치를 1로 만들기

# knowingAlp[i] = i번째 알파벳을 알고 있는지의 여부, 1 = 알고있음
knowingAlp = (1 << 26) - 1
for _ in range(m):
    o, x = input().split()
    idx = ord(x) - 97
    if o == '1': # 알파벳을 잊는다.
        knowingAlp &= ~(1 << idx)
    elif o == '2': # 알파벳을 기억한다.
        knowingAlp |= (1 << idx)
    
    # 해당 시점에 알고 있는 단어 수 출력
    wordsCount(knowingAlp)

 

[풀이 - 자바]

package PS;

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

public class B_18119 {
    static int n, m;
    static int[] words;
    static long knowingAlp;
    public static void wordCount(){
        int count = 0;
        for(Integer w : words){
            // 모든 알파벳을 다 알고 있는 경우에만 단어를 안다.
            if((knowingAlp & w) == w){
                count++;
            }
        }
        System.out.println(count);

    }
    public static void main(String[] args) throws Exception {
        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 int[n];
        // 주어진 단어들을 비트로 표현하기
        for(int i = 0; i < n; i++){
            String word = br.readLine();
            for(int j = 0; j < word.length(); j++){
                words[i] |= 1 << (int) word.charAt(j) - 97;
            }
        }
        // knowingAlp[i] = i번째 알파벳을 알고 있는지 여부
        knowingAlp = (1 << 26) - 1;
        for(int i = 0; i < m; i++){
            st = new StringTokenizer(br.readLine());
            int o = Integer.parseInt(st.nextToken());
            String x = st.nextToken();
            int idx = (int) x.charAt(0) - 97;
            if(o == 1){ // 알파벳을 잊는다.
                knowingAlp &= ~(1 << idx);
            }else{ // 알파벳을 기억한다.
                knowingAlp |= (1 << idx);
            }

            // 해당 시점에 알고 있는 단어 수 출력
            wordCount();
        }
    }
}