[백준] 1062번 가르침 (by Python)

문제

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

1062번: 가르침

 

풀이

    브루트 포스 방식으로 푸는 비트마스킹 문제이다. 처음에는 비트마스킹 방식이 익숙하지 않아서 set으로 시도해봤으나 시간 초과의 벽에 막혀 비트마스킹 방법으로 풀게 되었다.

 

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

def convert(x):
    return ord(x) - ord('a')

def convert_2(arr):
    result = 0
    for a in arr:
        result |= (1 << a)
    return result

n, k = map(int, input().split())
s = set([convert(a) for a in ['a', 'c', 'i', 'n', 't']])
base = 0
for i in s:
    base |= (1 << i)
arr = [set(map(convert, input().strip())) for _ in range(n)]
arr_2 = [convert_2(a) for a in arr]
candidates = set().union(*arr) - s
answer = 0
if k < 5:
    print(0)
else:
    if len(candidates) <= (k - 5):
        print(n)
    else:
        for c in combinations(candidates, k - 5):
            temp = base
            for i in c:
                temp |= (1 << i)
            temp ^= (1 << 26) - 1
            answer = max(answer, sum(1 if (temp & a) == 0 else 0 for a in arr_2))
        print(answer)

 

    기본적으로 모든 단어에 포함되어있는 'antatica'에 있는 알파벳 집합 {'a', 'c', 'i', 'n', 't'} 를 가지고 있는 수를 비트마스킹을 통해 표현한다. 단어는 모두 영어 소문자로 표현되어있다는 것이 명시되어 있으므로, 'a'부터 'z'까지를 각각 0~25의 수에 mapping 후 비트연산을 해주어 base를 만든다. 만약 k가 5보다 작을 경우 base에 있는 알파벳들을 모두 포함하는 것이 불가능하므로 자연스럽게 답은 0이 된다.

    카운트를 하기 위해 각 단어마다 추가적으로 필요한 알파벳을 비트마스킹된 형태로 저장하는 리스트 arr_2와 고를 수 있는 알파벳 후보군이 모두 담긴 집합 candidates를 둔다. 만약 candidates의 원소 개수가 (k - 5)보다 작거나 같을 경우, 모든 단어를 알 수 있을 만큼 충분한 알파벳을 가르칠 수 있다는 뜻이기에 답은 n이다. 예외처리를 해주지 않을 경우, combinations 라이브러리는 이런 경우에 그냥 지나가므로 주의해야 한다. 그 외의 경우, candidates에서 (k - 5)개의 알파벳 조합들 중 어느 것이 가장 많은 단어를 표현할 수 있는지 세면 되는 방식이다.

    개인적으로 list에 포함된 set들을 한꺼번에 union하는 방법을 배우고, 비트마스킹에서 포함관계를 비교하는 식 (XOR 후 AND 비교)을 알게 돼서 많이 배운 문제였다.