[백준 1062번-파이썬/Python] 가르침

http://acmicpc.net/problem/1062

{코드}

from itertools import combinations
n, k = map(int, input().split())
if k < 5:
    print(0)
else:
    k -= 5
    nece_chars = {'a', 'n', 't', 'i', 'c'}
    input_chars = []
    alpha = {ky: v for v, ky in enumerate(
        (set(map(chr, range(ord('a'), ord('z')+1))) - nece_chars))}
    cnt = 0
    for _ in range(n):
        tmp = 0
        for c in set(input())-nece_chars:
            tmp |= (1 << alpha[c])
        input_chars.append(tmp)
    power_by_2 = (2**i for i in range(21))
    for comb in combinations(power_by_2, k):
        test = sum(comb)

        ct = 0
        for cb in input_chars:
            if test & cb == cb:
                ct += 1

        cnt = max(cnt, ct)
    print(cnt)

{설명}

먼저, 어떤 단어이든 a, n, t, i, c의 글자는 무조건 배워야 하기 때문에 k가 5보다 작으면 어떤 단어도 배울 수 없습니다.

그러면 5보다 큰 경우를 생각해야 하는데, 처음에는 집합을 통해서 바로 풀 수 있을 줄 알았는데 시간 초과나 틀렸다고 떠서 문제 분류에 비트마스킹이 있는 것을 보고 비트마스킹으로 푸는 방향으로 바꿨습니다.

비트마스킹을 간단히 설명하자면, 비트를 움직여 어떤 행동을 했는지 안 했는지를 빠르게 파악할 수 있는 방법입니다.

예를 들어 1~5까지의 마을이 있고 이를 랜덤한 순서로 방문한다면 1번 마을을 방문하면 00001, 2번 마을은 00010, (4, 5) 번 마을을 방문하면 11000등으로 표현할 수 있는 것이죠.

이를 이용해 먼저 필수 알파벳을 제외한 나머지 알파벳에 각각 정수 값을 할당하고(아스키코드를 사용해도 상관없습니다만 경우에 따라 수가 매우 커질 수 있기에 기왕이면 최소화하는 것이 좋을 것 같습니다) 딕셔너리로 저장합니다.

그러면 입력받은 각 단어에 대해서 필수 알파벳을 제외한 나머지 알파벳에 딕셔너리에 저장된 값을 통해 시프트 연산으로 해당 알파벳이 필요하다는 것을 저장합니다.

*<<연산자는 왼쪽 시프트로 1<<3은 0b1000이 되고, |는 or 연산자로 두 수를 이진수로 표현하면 어떤 자리에 둘 중 하나라도 1이라면 해당 자리를 1로 저장합니다. 1001과 0110은 1111이 되는 것이죠.

그 뒤에는 조합(combination)함수를 이용해 2^n들 중에서 k-5(코드에서는 이미 k-5를 위에서 했기 때문에 또 하지 않았습니다) 개를 선택합니다.

*range가 21인 이유는 알파벳이 총 26개인데 5개는 이미 배웠으며 딕셔너리에는 enumerate를 사용해 0부터 20까지의 수가 임의로 설정되었기 때문입니다.

나온 조합의 합이 새롭게 배운 알파벳을 의미하며 &(and)연산을 하면 비트가 둘 다 1일 때 1을 저장하기에 test가 11010이면 cb가 10010일 때 10010이 되어 cb와 같게 됩니다. 그런데 test가 00010인 경우는 00010이 되기에 cb와 같지 않게 되죠.

cb와 같다는 것은 적어도 cb의 1인 비트들은 test에 전부 포함되어 있다는 뜻이므로 카운트를 증가시킵니다.

그래서 이 카운트들의 최댓값이 답이 되죠.

** 비트 연산에 익숙하지 않으시면 따로 찾아보시기를 추천합니다.