가르침 (1062번) - 백준 (BOJ)

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

1062번: 가르침

 

 

백준 - 가르침 (1062번)

자료구조&알고리즘 : Combinations (조합) & Bitmask (비트마스크)

난이도 : Gold 4

 

---

 

처음에 비트마스크 안 쓰고 그냥 리스트로 기록해서 풀었는데

PyPy3에서는 통과했지만, Python3는 시간 초과가 나왔다.

 

그래서 Bitmask를 적용했더니 Python3에서도 통과했다.

 

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


class Teach():
    def __init__(self, N, K):
        self.answer = 0
        if K == 26:
            self.answer = N
        elif 5 <= K:
            base = set('acint')
            words = [{c for c in input().rstrip()[4:-4] if c not in base} for _ in range(N)]
            all_chars = set()
            for word in words:
                all_chars = all_chars.union(word)
            self.tot_len = len(all_chars)
            if self.tot_len <= K-5:
                self.answer = N
            else:
                atoi = {c: i for i, c in enumerate(all_chars)}
                words = [sum(1<<atoi[c] for c in word) for word in words]
                self.answer = self._teach_words(words, K)
    

    def _teach_words(self, words, K):
        answer = 0
        for seq in comb((1<<i for i in range(self.tot_len)), K-5):
            mask = sum(seq)
            answer = max(answer, sum(mask&word == word for word in words))
        return answer


if __name__ == '__main__':
    teacher = Teach(*map(int, input().split()))
    print(teacher.answer)

 

 

① 반드시 들어가야 하는 ['acint'] 를,

입력으로 받는 N개의 단어들(words)에서 모두 제거한다.

 

 

 

② Combinations를 활용해서, words에 존재하는 모든 철자들 중 (K-5)개를 뽑는 조합을 모두 탐색한다.

(K-5인 이유는, 'acint'를 제거했기 때문이다.)

 

 

 

③ 위 조합의 각 경우의 수에 해당하는 철자들로,

몇 개의 단어들을 읽을 수 있는지 센다.

(Bitmask를 활용해서 이 과정을 최적화할 수 있다.)

 

그 중 가장 큰 값을 반환한다.