백준 1062번 가르침 (Python 3)

 

Baekjoon online judge 1062번 파이썬

 

링크

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

1062번: 가르침

남들은 다 비트마스킹가지고 풀더라

우선 antic, 이 다섯 문자는 무조건 가지고 있어야한다. 따라서 k가 5보다 작다면 0을 출력한다.

combination을 이용해서 antic,을 제외한 문자를 선택한 경우의 수를 구한다.

입력을 set으로 바꾸고, antic를 빼준다. (차집합)

이제 우리가 선택한 경우의 수에서 issubset을 이용해 입력이 우리가 선택한 경우의 수의 부분집합인지 확인한다.

 

소스코드

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

n,k=map(int,input().split())
alpha=['b','c','d','e','f','g','h','j','k','l','m','o','p','q','r','s',
       'u','v','w','x','y','z']


now_max=-1
if k>=5:
    possible=list(combinations(alpha,k-5))
    temp={'a','n','t','i','c'}

    s=list()
    for _ in range(n):
        s.append(set(input().rstrip())-temp)

    for p in possible:
        a=set(p)
        cnt=0
        for k in s:
            if k.issubset(a):
                cnt+=1
        now_max=max(now_max,cnt)
    print(now_max)
else:
    print(0)