[Baekjoon] 1062. 가르침

🔗 Problem Link

https://www.acmicpc.net/problem/1062

---

❔Thinking

• 정해진 개수의 알파벳 조합을 만들 때, 해당 알파벳들로 만들 수 있는 단어의 최대 개수를 반환한다.
• anta, tica가 앞 뒤로 붙기 때문에, 총 5개의 알파벳은 조합에 무조건 포함되어야 한다. 

---

💻Solution

import sys
from itertools import combinations
input = sys.stdin.readline

N, K = map(int, input().split())
words = []
for _ in range(N):
    word = input().rstrip()
    words.append(set(word[4:-4]))
if K < 5:
    print(0)
else:
    base = {'a','n','t','i','c'}
    needed = set()
    for w in words:
        for char in w:
            if char not in base:
                needed.add(char)
    if len(needed) + 5 <= K:
        print(N)
    else:
        combis = combinations(needed, K-5)
        answer = 0
        for combi in combis:
            learned = set(combi) | base
            tmp_cnt = 0
            for w in words:
                for char in w:
                    if char not in learned:
                        break
                else:
                    tmp_cnt += 1
            answer = max(answer, tmp_cnt)
        print(answer)

---

🗝️keypoint

1. 주어진 단어들에 등장하는 모든 알파벳의 조합을 구하는 것이, 26개의 알파벳 조합을 확인하는 것 보다 빠르다.
2. 두 집합의 차집합을 확인하는 방법보다, 문자를 하나하나 확인하고 break를 두는 방법이 더 빠르다.
3. 단어의 개수와 알파벳의 개수가 적어 모든 경우를 다 확인할 수 있을때, 적절한 조건으로 break 하는 방법을 생각해야 한다.