[백준] 1062번 : 가르침

1062번: 가르침

가능한 알파벳을 모두 만들어본뒤, 해당 알파벳을 비트 단위로 본다. 즉 비스마스킹을 한다.

예를들어 알파벳이 4개 존재햇을때 abcd라는 단어인경우 0x1111 로 표현 할 수 있고, abc인경우 0x0111로 표현 할 수 있다. 우리는 알파벳 a~z까지 있는 경우이니 0x00000..00 이 필요하다.

그래서 가능한 모든 알파벳을 구한뒤, 해당 알파벳이 있는지 없는지 여부는 비트연산을 통하여 문제를 해결 할 수 있다.

import sys
from itertools import combinations
input = sys.stdin.readline

N, K = map(int, input().split())
words = [0 for _ in range(N)]
for i in range(N):
    temp = str(input().strip())
    for j in range(len(temp)):
        cost = ord(temp[j]) - ord('a') + 1
        if not (words[i] & (1 << cost)):
            words[i] |= (1 << cost)

alpa = [i for i in range(1, 27)]
ans = 0
if K > 4:
    for check in combinations(alpa, K):
        temp = 0
        cnt = 0
        for c in check:
            temp |= (1 << c)

        for word in words:
            if (temp & word) == word:
                cnt += 1

        if cnt > ans:
            ans = cnt
    print(ans)
else:
    print(0)