[엘리스] 엘리스의 동물어 수업

엘리스의 동물어 수업

코더랜드에는 말을 할 수 있는 동물들이 모여사는 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어의 단어가 주어집니다. 이 단어는 중복 되지 않음이 보장됩니다.

출력

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

모범 답안

• a, i, k, n, s는 모든 단어에 들어가므로 5개를 제외
• 3가지 경우로 나누어서 dfs를 진행
  • 1. 알파벳을 모두 추가한 경우
       • 단어별로 몇개나 학습이 가능한지 계산
       • 가장 긴 숫자를 반환
  • 2. 알파벳을 하나도 추가하지 않은 경우
       • a부터 z까지 차례대로 하나씩 넣어보면서 진행
  • 3. 알파벳을 하나라도 추가한 경우
       • 추가한 알파벳 이후로 조사(알파벳은 순서가 상관없기에 무방)

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

    # a, i, k, n, s이외의 알파벳을 하나도 추가하지 못한 경우 
    elif len(st) == 0:
        # ord는 문자열을 순자로 반환 <-> char는 숫자를 문자열로 반환 
        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))

    # a, i, k, n, s이외의 알파벳을 하나라도 추가한 경우 
    else:
        # 추가한 알파벳이후로 계산 
        # 알파벳은 순서가 상관없기에 st[-1]이후로 해줘도 무방함 
        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)

 

출처 : 엘리스 아카데미, https://academy.elice.io/learn