K개의 알파벳을 배워 최대의 단어를 읽을 수 있도록 하는 방법. 모든 단어는 anta 로 시작하며 tica로 끝남.
백트래킹을 통해서 모든 경우의 수를 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)
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)
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)