[BOJ/백준] 18119 단어 암기 파이썬

문제 풀이 : https://www.acmicpc.net/problem/18119

18119번: 단어 암기

 

시간초과가 계속 나서 비트마스크로 겨우 푼 문제이다.

 

일단 word를 전처리해야한다.

알파벳을 0~26 비트로 처리하자

0번째 비트는 a의 등장 유무

1번째 비트는 b의 등장 유무

이런식으로 처리된다.

word에 포함된 알파벳을 비트로 표현해서 저장한다.

 

모음의 경우 처리를 해주지 않았다.

입력이 o, x라 들어올 때

o가 1일 때는 x를 기억하고 있었음이 보장되고, o가 2일 때는 x를 잊고 있었음이 보장된다. 라고 되어 있다. 그리고 모음은 절대 잊지 않는다고 하기 때문에 모음에 대한 연산이 주어지지 않는다.

 

시작할 때 모든 알파벳을 기억하고 있는다고 한다. 그렇기 때문에 초기 본인이 알고 있는 알파벳을 2^26-1로 초기화하자.

비트는 0번째 비트부터 시작하기 때문에 2^26은 왼쪽에서 27번째 1비트가 1인 것이다. 여기서 -1을 해주면 26개자리가 모두 1이 된다.

 

연산은 알파벳 빼기, 넣기 두 종류이다.

알파벳 빼기는 해당 자리 비트를 0으로 바꾸면 된다. 이는 AND 연산을 사용하자

특정 자리 비트를 1로 바꾸기 위해서는 NOT 연산을 활용해야한다. AND는 0이 하나라도 있으면 0으로 처리된다.

그래서 1111 AND (1<<2) 하게 되면 1111 AND 0010으로 처리가 된다. 그러므로 뒤에 녀석을 NOT 처리해서 연산하자

1111 AND ~(1<<2) 하게 되면 1111 AND 1101이 되고 결과는 1101이 된다.

 

넣기는 해당 자리 비트를 1로 바꾸면 된다.

이는 그냥 OR 연산 해주면 된다.

OR는 둘중 1이면 무조건 1이 된다.

 

명령에 따라 현재 기억하고 있는 알파벳을 수정했다면

모든 단어를 돌아다니면서 해당 단어의 비트가 포함됐는지 확인하자.

이는 AND 연산을 하자.

앞에서 말했던 것 처럼 AND는 0이 하나라도 있으면 0이 된다 했다.

그렇기 때문에 내가 기억하고 있는 알파벳 비트와 단어의 비트를 AND 연산을 해서 단어 비트가 나온다면 단어에 포함된 모든 알파벳을 기억하고 있다는 것이다.

예를 들어 알파벳이 1111 1111 이고 단어가 0000 0010 이라면

AND 연산을 수행한 결과는 0000 0010 일 것이다.

 

이를 활용해서 개수를 세어주자.

 

from sys import stdin,stdout

input = stdin.readline
print = stdout.write
trans = lambda c : ord(c)-ord('a')
n,m = map(int, input().split())

words = []
for _ in range(n):
    word = input().strip()
    bitmask = 0
    for c in word:
        idx = trans(c)
        bitmask |= (1<<idx)
    words.append(bitmask)

def solv():
    global words
    alpha = 2**26-1

    for _ in range(m):
        op,c = input().strip().split()
        alpha_idx = trans(c)

        if op == '1':
            alpha &= ~(1<<alpha_idx)
        else:
            alpha |= (1<<alpha_idx)

        cnt = 0
        for word in words:
            if alpha & word == word:
                cnt += 1
        print('%d\n'%cnt)
solv()