백준 1062: 가르침 - 비트마스크, 조합

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

1062번: 가르침

조합과 비트마스크로 풀 수 있는 문제입니다.

 

모든 단어들은 'anta'로 시작하고 'tica'로 끝나므로 'a c i n t' 이 5개는 꼭 배워야합니다.

만약 k가 5보다 작다면 'a c i n t'를 모두 배울 수 없으므로 답은 0이 됩니다.

 

k가 5보다 크다면 'anta'와 'tica' 사이의 단어들을 추출한 뒤 'a c i n t'를 제거해줍니다.

그 후, 비트마스크로 풀기 위해 'a c i n t'가 소거된 단어 리스트들을 모두 비트연산을 할 수 있도록 해줍니다.

 

예를 들어 'antabadftica'에서 'anta'와 'tica'를 뺀 'badf'에서 'a'를 제거하면 'bdf'가 됩니다.

그 후 a는 0의 기준을 잡고 비트연산을 할 수 있도록 변환해줍니다.

mask = 0

 

b = 1

mask = mask | 1 << 1

(0 | 10)

 

d = 3

mask = mask | 1 << 3

(10 | 1000 -> 1010)

 

f = 5

mask = mask | 1 << 5

(1010 | 100000 -> 101010)

 

그럼 이 것은 각 자리수가 가리키는 알파벳을 배워야한다는 것을 의미합니다.

 

z...f e d c b a

0..1 0 1 0 1 0

 

이렇게 변환 된 것을 배워야 할 알파벳들의 모든 경우의 수와 비교하여 제일 많이 배울 수 있는 경우를 찾으면 됩니다.

 

조합으로 뽑을 수 있는 경우의 수를 줄이기 위해 단어를 입력 받을 때  set에 'a c i n t'를 제외한 알파벳들을 넣어줍니다.

(a부터 z까지의 모든 알파벳에서 뽑는 것이 아닌, 현재 입력된 단어들의 알파벳만)

 

그 후 조합의 결과 하나 하나를 기준으로 for문을 돌아 해당 알파벳들로 몇 개의 단어를 배울 수 있는 지 확인합니다.

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

common_alphabet = {'a','c','i','n','t'}
input_word = []

input_alphabet_set = set()
n, k = map(int, input().split())
k -= 5

for nn in range(n):
    # anta [필요한 것들] tica, 그리고 필요한 것들에서 a c i n t 제거
    word = set(input().rstrip()[4:-4]).difference(common_alphabet)
    # a c i n t를 제외하고 나타난 알파벳 목록들 (중복 X)
    input_alphabet_set.update(word)
    # a c i n t를 소거한 단어 리스트
    input_word.append(list(word))

if k < 0:
    print(0)
    exit()

# a c i n t를 소거한 단어 리스트를 비트연산 할 수 있도록 변경 
input_word_bit = []
for ii in input_word:
    current_bit = 0
    for alpha in ii:
        current_bit |= 1 << ord(alpha) - ord('a')
    input_word_bit.append(current_bit)

combi = cb(input_alphabet_set, min(k, len(input_alphabet_set)))
max_count = 0
for cc in combi:
    count = 0
    alphabet_bit = 0
    for alpha in cc:
        alphabet_bit |= 1 << ord(alpha) - ord('a')
    for ii in input_word_bit:
        if alphabet_bit & ii == ii:
            count +=1
    max_count = max(max_count, count)

print(max_count)