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

백준 #18119 단어 암기

• 백준 18119번 단어 암기 문제풀기

• PyPy3으로 제출해야 한다.

1. 완전 탐색 (비트마스크)

• PyPy3 3464 ms

import sys
input = sys.stdin.readline

def solution(N, M):
    strings = []

    vowels = 'aeiou'
    cons = 'bcdfghjklmnpqrstvwxyz'
    
    weight = dict()
    for i in range(len(cons)):
        weight[cons[i]] = i

    for i in range(N):
        temp = set()
        for char in input().strip():
            temp.add(char)
                
        num = 0
        for char in temp:
            if char in vowels: continue
            num += 1 << weight.get(char)
        
        strings.append(num)
    
    current = (1 << 21) -1
    for i in range(M):
        o, x = input().split()
        if o == '1':
            current -= 1 << weight.get(x)
        else:
            current += 1 << weight.get(x)
        
        num = 0
        for string in strings:
            if current & string == string: num += 1
        
        print(num)

if __name__ == '__main__':
    solution(*map(int, input().split()))

2. 최적화 (비트마스크)

• PyPy3 912 ms
• 각 알파벳이 들어있는 단어만 체크하는 방식을 취했다.
  • 모든 입력으로 a~z 알파벳이 모두 들어있는 단어가 들어올 경우 위의 방법과 속도차이가 나지 않을 것이다.

import sys
input = sys.stdin.readline

def solution(N, M):
    vowels = 'aeiou'
    cons = 'bcdfghjklmnpqrstvwxyz'
    
    weight = dict()
    strings = dict()
    for i in range(len(cons)):
        weight[cons[i]] = i
        strings[cons[i]] = []
    

    for i in range(N):
        temp = set()
        for char in input().strip():
            temp.add(char)
                
        num = 0
        for char in temp:
            if char in vowels: continue
            num += 1 << weight.get(char)
        
        for char in temp:
            if char in vowels: continue
            strings.get(char).append(num)
    
    current = (1 << 21) -1
    for i in range(M):
        o, x = input().split()
        if o == '1':
            for string in strings.get(x):
                if current & string == string: N -= 1
            current -= 1 << weight.get(x)
        else:
            current += 1 << weight.get(x)
            for string in strings.get(x):
                if current & string == string: N += 1
        
        print(N)

if __name__ == '__main__':
    solution(*map(int, input().split()))