[Baekjoon-Python] 1062 : 가르침

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

접근

비트마스크를 적용하기 위해 알파벳을 아스키코드 - 97로 치환한다.
"anta", "tica"를 구성하는 a, c, i, n, t도 K개에 포함된다.
알파벳을 K개 조합해서 비트 연산으로 단어를 몇 개 읽을 수 있는지 계산한다.

풀이

from sys import stdin
from itertools import combinations

n, k = map(int, stdin.readline().split())
if k < 5: # (1)
    print(0)
elif k == 26: # (2)
    print(n)
else:
    k -= 5 # (3)
    no_learned = set()
    words = []
    for _ in range(n):
        w = 0
        for i in set(stdin.readline().rstrip()) - {"a", "c", "i", "n", "t"}:
            alphabet = 1 << ord(i) - 97 # (4)
            w |= alphabet
            no_learned.add(alphabet)
        words.append(w)

    if len(no_learned) <= k: # (5)
        print(n)
    else:
        ans = 0
        for comb in combinations(no_learned, k): # (6)
            tmp = 0
            for c in comb:
                tmp |= c

            cnt = 0
            for word in words:
                if word & tmp == word: # (7)
                    cnt += 1
            ans = max(ans, cnt)
        print(ans)