[ 1062 ] [ bit-masking, combination ] 가르침

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

1062번: 가르침

 

---

풀이 과정

---

1. 일단 기본적으로 anta, tica라는 단어가 들어간다.
   
   • 여기서, 알파벳 ['a', 'n', 't', 'i', 'c']는 기본적으로 무조건 들어가야 된다는 점을 알 수 있음.
2. 따라서, K가 5보다 작은 경우는 불가능하므로 0을 출력해주면 되고, 5보다 큰 경우는 두가지로 나눌 수 있다.
   1. 기본적으로 ['a', 'n', 't', 'i', 'c']는 들어가야 함.
   2. (1)에서 제외한 알파벳들 중 (K-5)개를 뽑음.
   3. 1번과 2번을 합치면 하나의 케이스가 된다.
3. 각각의 케이스별로 총 몇개의 단어를 읽을수 있는지 체크하고, 최댓값을 갱신하면 된다.
4. 위 과정을 Set 자료구조로 하였는데.. 자꾸 메모리 초과가 나와서 풀이를 좀 찾아보니 비트 마스킹 기법을 사용한다고 한다. 알파벳 위치를 기준으로 비트 '1'을 이동시키는 방식
   • a인 경우 001, b인 경우 010, c인 경우 100, ...  , ab인 경우 011, ...
   • 전체 단어들에 대해 각 단어들을 알파벳 별로 미리 비트화를 시켜준다. 
     • hello의 경우, 알파벳이 h,e,l,o가 있으므로 대응되는 비트값을 1로 수정
   • 각각의 케이스 비교단계에서 케이스 또한 비트화를 시켜준 다음 and 연산자를 해준다.
     • 케이스에서 ['a', 'n', 't', 'i', 'c', 'k']를 뽑았다고 할 때,  단어가 antic인 경우 모두 공통적으로 a, n, t, i, c의 비트가 1로 조정되어 있으므로, and연산자를 해주면 a,n,t,i,c에만 1로 지정되어 있을 것이다.
   • and 연산자의 결과가 케이스의 비트와 같은 경우 읽을 수 있는 단어이므로 카운팅

비트 마스킹이 set보다는 빠르므로 set이 속도 문제로 안된다면, 고려해보아야 한다는걸 배우게 되었다..

---

소스 코드

---

import sys
from itertools import combinations

input = lambda: sys.stdin.readline().rstrip()
N, K = map(int, input().split())
words = [0] * N
base = ['a', 'n', 't', 'i', 'c']
for i in range(N):
    word = list(input())[4:-4]
    for ch in word:
        words[i] |= (1 << ord(ch) - ord('a'))
        
answer = 0
if K < 5:
    pass
else:
    alpha = 'bdefghjklmopqrsuvwxyz'
    append_case = list(combinations(list(alpha), K-5))
    for case in append_case:
        make_bit = 0
        for ch in base:
            make_bit |= (1 << ord(ch) - ord('a'))
        for ch in case:
            make_bit |= (1 << ord(ch) - ord('a'))

        count = 0
        for i in range(len(words)):
            if words[i] & make_bit == words[i]:
                count += 1
        
        answer = max(answer, count)
        
print(answer)