[Python 3] BOJ - 1062 "가르침"

 # 문제 링크 : https://www.acmicpc.net/problem/1062

1062번: 가르침

 

 # 풀이 : 

 개인적으로 이 문제의 핵심은 문자열 비교를 비트마스킹으로 하는 것이라고 생각한다. 문제의 조건에 따라 A, C, N, T, I는 필수적으로 들어가야 하므로 총 알파벳 26개 중 21개만 가능한 후보군이 된다. 따라서 만일 K가 5 미만이라면 어떠한 글자도 읽을 수 없다.

 만일 K가 5 이상이라면 총 21개 중 K - 5개를 뽑는 조합의 경우와 같다. 여기서 뽑은 조합의 비트마스킹 수에 단어에 해당하는 비트마스킹이 포함되어 있다면 읽을 수 있으므로 각 경우마다 읽을 수 있는 단어 수를 알 수 있고 이것의 최대값을 정답으로 출력하면 된다

<그림 1. a,b,c의 조합 비트마스킹>

 위 그림 1은 배열 [a,b,c]의 부분집합을 그림으로 나타낸 것이다. 그런데, 있다 혹은 없다는 2가지 상태로 나타낼 수 있기 때문에 각 원소가 있는지 없는지를 이진수로 표현하고 이를 정수로 바꿔서 생각할 수도 있다. 즉, 어떤 문자의 부분집합을 하나의 정수로 나타낼 수 있기에 훨씬 비교가 빨라진다. 

<그림 2. 비교 예시>

 위 그림 2는 실제적으로 각 부분집합의 비교를 나타낸 것이다. 현재 정수 3은 a,b를 포함한 부분 집합이고, 정수 1은 a만 포함한 부분집합이다. 따라서 [a]는 [a.b]에 포함되므로 AND 연산을 통해 1이 나오면 포함되었다고 할 수 있고 0이 나오면 포함되지 않았음을 알 수 있다.

 파란색 글자는 위와 아래의 숫자가 같음을 의미하고, 빨간색은 위와 아래의 숫자가 같지 않음을 의미한다. AND 연산은 위아래가 같은 숫자라면 그 숫자를 그대로 취하고, 같지 않다면 0으로 나타내는 연산이다.

 

 # 코드

import sys, itertools

# n, m 입력
n,m = map(int, sys.stdin.readline().split())

# words : 각 단어의 비트마스킹한 정수를 저장
words = [0] * n
ans = 0
for i in range(n):
    temp = sys.stdin.readline().rstrip()
    # word 배열에 각 문자의 비트마스킹 저장
    for x in temp:
        words[i] |= (1 << (ord(x) - ord('a')))
        
# 만일 m이 5미만이면 필수 글자를 다 배울 수 없기 때문에 한 단어도 읽지 못한다
if m < 5:
    print(0)
else:
    # candidiate : 필수 글자를 제외한 알파벳
    # need : 필수 알파벳
    candidiate = ['b','d','e','f','g','h','j','k','l','m','o','p','q','r','s','u','v','w','x','y','z']
    need = ['a','c','t','i','n']
    for i in list(itertools.combinations(candidiate, m - 5)):
        each = 0
        res = 0
        # 각 조합에 대한 비트마스킹
        for j in need:
            each |= (1 << (ord(j) - ord('a')))
        for j in i:
            each |= (1 << (ord(j) - ord('a')))
            
        # 단어와 각 조합의 비교
        for j in words:
            if each & j == j:
                res += 1
                
        # 최대값 갱신
        if ans < res:
            ans = res
    print(ans)