(Elice / 완전탐색 / Python) 엘리스의 동물어 수업

엘리스의 동물어 수업

코더랜드에는 말을 할 수 있는 동물들이 모여사는 aniski 나라가 있습니다. 이 나라의 동물들은 aniski어라는 조금 특별한 언어를 사용합니다. aniski어는 특이하게도 모든 말을 “ani”로 시작해서 “ski”로 끝이 납니다.

엘리스는 이 나라에 동물어 학습지를 판매 하고 있습니다. 홍보를 위해 짧은 시간 동안 동물 어린이들에게 글자를 가르쳐서 얼마나 효과가 좋은 지 증명하려고 합니다. 엘리스가 몇 개의 글자를 가르쳤을 때 동물 어린이들이 배울수 있는 단어는 몇 개나 될까요?

 

입력 예시 1

7
3
anircski
anihelloski
anirzcski

출력 예시 1

1

입력 예시 2

8
3
anircski
anihelloski
anirzcski

출력 예시 2

2

 

입력

• 첫 번째 줄에 엘리스가 가르친 글자의 숫자가 주어집니다. 이 글자의 수는 0이상 26이하의 알파벳 소문자입니다.
• 두 번째 줄에는 aniski어의 단어의 수가 주어집니다. 이 수는 1이상 100 이하 입니다.
• 세 번째 줄부터 aniski어의 단어가 주어집니다. 이 단어는 중복 되지 않음이 보장됩니다.

출력

• 학생들이 읽을 수 있는 단어의 개수의 최댓값을 출력하세요.

소스 코드

def to(st):
    tl = st.replace('a','').replace('i','').replace('k','').replace('n','').replace('s','')
    return tl

def ct(st, tst):
    for x in st:
        if x not in tst: return False
    return True

def gs(st):
    global max_word

    if len(st) == k:
        this_len = 0
        for x in range(n):
            if ct(s[x], st): this_len += 1
        if max_word < this_len: max_word = this_len
    elif len(st) == 0:
        for x in range(ord('a'), ord('z') + 1):
            if x == ord('a') or x == ord('i') or x == ord('k') or x == ord('n') or x == ord('s'): continue
            gs(st + chr(x))
    else:
        for x in range(ord(st[-1]) + 1, ord('z') + 1):
            if x == ord('a') or x == ord('i') or x == ord('k') or x == ord('n') or x == ord('s'): continue
            gs(st + chr(x))

k = int(input())
n = int(input())
s = []

max_word = 0
k -= 5

for x in range(n): 
    s.append(to(input()))

if k < 0: 
    print(0)
else:
    gs('')
    print(max_word)