1062번_가르침.py

[문제 설명]

K개의 알파벳을 배워 최대의 단어를 읽을 수 있도록 하는 방법. 모든 단어는 anta 로 시작하며 tica로 끝남.

[문제 풀이]

1. set과 백트래킹을 이용하는 방법
2. combination을 통해서 푸는 방법

1. set과 백트래킹

백트래킹을 통해서 모든 경우의 수를 check.
이때 유망성 check를 set()을 통해서 진행.

import sys
input = sys.stdin.readline
answer = 0
n, k = map(int, input().split())

if k < 5 or k == 26:
    answer = 0 if k < 5 else n
    print(answer)
    exit(0)
    
words = []
for _ in range(n):
    temp = input()
    words.append(temp[4:len(temp)-5]) # 앞 뒤에 반복되는 부분은 자르고 list에 넣는다.
learn = set('antic')

def dfs(idx, cnt):
    global answer
    # 배울 수 있는 알파벳의 개수 도달. 
    # 단어를 읽을 수 있는 지 check
    if cnt == k - 5:
        check = 0
        for word in words:
            for a in word:
                if set(a) - learn:
                # .issubset(a)
                    break
            else:
                check += 1
        answer = max(answer, check)
        return
    # 백트래킹을 통해서 모든 경우의 수를 확인 
    for i in range(idx, 26):
        alpha = chr(97 + i)
        if set(alpha) - learn:
            learn.add(alpha) # set의 add(), remove() 모두 O(1)
            dfs(i, cnt + 1)
            learn.remove(alpha)


dfs(0, 0)
print(answer)

2. combination을 통해

combination을 통해서 배울 수 있는 k-5개의 알파벳의 조합을 모두 구하고 가장 많은 단어를 배우는 경우의 수를 출력
이때 배워야할 알파벳보다 배울 수 있는 알파벳이 많을 수도 있는 경우를 처리하고 넘어가야함!

import sys
from itertools import combinations

n, k = map(int, input().split())
words = []
alphabet = set()
for _ in range(n):
    temp = input()
    words.append(set(temp) - {'a', 'n', 't', 'i', 'c'} )# 앞 뒤에 반복되는 부분은 자르고 list에 넣는다.
    alphabet |= set(temp)

if k < 5 or k == 26:
    answer = 0 if k < 5 else n
    print(answer)
    sys.exit()

alphabet = alphabet - set('antic')
alpha_combs = combinations(alphabet, k - 5)
if len(alphabet) <= k -5 :
    print(n)
    sys.exit()

answer = 0
for comb in alpha_combs:
    comb = set(comb)
    cnt = 0
    for word in words:
        if word.issubset(comb):  # word <= comb
            cnt += 1
    # 최대값 갱신
    if cnt > answer:
        answer = cnt

print(answer)

3. 추가 풀이 방법_모든 경우의 수

import sys
from itertools import combinations

n, k = map(int, input().split())
words = [set(input()) - {'a', 'n', 't', 'i', 'c'} for _ in range(n)]
answer = 0
# print(words)
if k < 5 or k >= 26:
    answer = 0 if k < 5 else n
    print(answer)
    sys.exit()

alpha_set = set("abcdefghijklmnopqrstuvwxyz") - set('antic')
alpha_combs = combinations(alpha_set, k - 5)

for comb in alpha_combs:
    comb = set(comb)
    cnt = 0
    for word in words:
        if word.issubset(comb):  # word <= comb
            cnt += 1
    # 최대값 갱신
    if cnt > answer:
        answer = cnt

print(answer)