iamyoungbin

You’ll never forget my name

1 분 소요

Problem

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

Idea

우선 남극의 모든 언어는 ‘anta’로부터 시작해 ‘tica’로 끝나므로 모든 단어에 ‘a’, ‘n’, ‘t’, ‘i’, ‘c’ 다섯 글자는 반드시 포함된다. 따라서 가르칠 수 있는 글자의 갯수인 K가 5보다 작다면 어떠한 단어도 만들 수 없다.

K가 5 이상인 경우 가르칠 단어들을 받아올 때마다 집합 자료형 set을 이용해 각 단어마다 들어간 글자들을 구해 리스트에 저장했다. 이 때 위의 다섯 글자는 모든 반드시 포함되어야 하므로 제외했다.

이후, 모든 알파벳 집합에서 반드시 필요한 글자 집합을 뺀 뒤, combinations를 이용해 각 케이스마다 가르칠 K-5 개의 글자들을 선택하며 완전 탐색했다. 가르칠 글자 집합을 통해 해당 단어를 배울 수 있는지에 대한 여부는 해당 단어의 글자 집합이 가르칠 글자 집합의 부분 집합일 경우에( target_word_letters ⊂ learned_letters ) 참이 된다. 이를 set의 메소드인 issubset으로 구현했다.

Code

import sys
from itertools import combinations

input = sys.stdin.readline

N, K = map(int, input().split())
word_set = []
essential = {'a', 'n', 't', 'i', 'c'}
letters = set([chr(i) for i in range(ord('a'), ord('z')+1)]) - essential

if K < 5:
    print(0)
else:
    for _ in range(N):
        temp = set(input().rstrip()) - essential
        word_set.append(temp)
    
    sol = 0
    for choice in combinations(list(letters), K-5):
        choice = set(choice)
        cnt = 0
        
        for w in word_set:
            if w.issubset(choice):
                cnt += 1
                
        sol = max(sol, cnt)
        
    print(sol)

Comment

초기에 가르칠 글자를 구하기 위해 만드는 집합을 (전체집합 - essential)이 아닌 (단어에서 한번 이상 사용되는 글자 집합 - essential)로 하면 더 효율적으로 구현할 수 있을 것이라 생각해서 그와 같이 구현했더니 계속 틀렸다. 같은 아이디어로 모집합만 전자로 바꾸었을 뿐인데 통과되었다. 후자에 뭔가 문제가 있어서 틀린 것 같은데 도대체가 무슨 오류가 있는지 모르겠다…

참고