Programming/Algorithm

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

oranz.23 2021. 3. 24. 17:13

문제

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

 

1062번: 가르침

첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문

www.acmicpc.net

 

풀이

    브루트 포스 방식으로 푸는 비트마스킹 문제이다. 처음에는 비트마스킹 방식이 익숙하지 않아서 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 비교)을 알게 돼서 많이 배운 문제였다.