January 14, 2023

1062번: 가르침

문제요약

• N개의 단어와 자연수 K가 주어지고 26개의 알파벳 중 K개의 알파벳만 읽을 수 때, 읽을 수 있는 단어의 수 출력
• 각 단어는 “anta”로 시작하여 “tica”로 끝난다.
• 1 ≤ N ≤ 50, 0 ≤ K ≤ 26

풀이

from itertools import combinations

N, K = map(int, input().split())
word_list = [input() for _ in range(N)]
arr = [1, 3, 4, 5, 6, 7, 9, 10, 11, 12,
       14, 15, 16, 17, 18, 20, 21, 22, 23, 24, 25]

result = 0

def check_readable(word, alpha_list):
    for char in word[4:len(word) - 4]:
        if (not alpha_list[ord(char) - 97]):
            return False
    return True

if (K < 5):
    print(0)
else:
    combination_list = list(combinations(arr, K - 5))
    for comb in combination_list:
        tmp_max = 0
        comb = list(comb) + [0, 2, 8, 13, 19]
        alpha_list = [i in comb for i in range(26)]

        for word in word_list:
            if (check_readable(word, alpha_list)):
                tmp_max += 1

        result = max(tmp_max, result)

    print(result)

• 필수로 포함되어야 하는 “a, n, t, i, c”를 제외한 21개의 알파벳의 조합을 구한다.
• 각 경우의 수에 대해서 몇개의 단어를 읽을 수 있는지 최댓값을 구한다.
• Dictionary를 사용하면 더 간결한 코드 작성 가능