(Python/🥇4)백준 알고리즘 1062번: 가르침

문제출처:https://www.acmicpc.net/problem/1062

1062번: 가르침

풀이:

 

문제를 보면 N, K 가 주어진다 , 

기본적으로 들어가는 단어 word 에는 aticn 총 5개가 들어간다.

즉 K가 5보다 작게되면 만들 수 있는 단어가 없게된다.

 

candidate = 저 5개 문자를 뺀 문자를 넣어누고

words 에는 N개 만큼 단어들을 가져온다

remain_sets 에는 N개의 단어들에서 words 에 있는 문자들을 빼주면 된다.

antarctica
antahellotica
antacartica

이거를 돌려서 remain_set 을 하면
[{'r'}, {'o', 'l', 'e', 'h'}, {'r'}] 가 들어간다

 

이 문제 접근은 

일단 K<5 이면 0 으로 프린트하고 끝내고

아니면

K-5 를 뺸다 이유는 5개는 필수로 배워야 하는 언어이다 . (word)

뺀 것을 combinations 해줘서 모든 경우의 수를 가져오고

lst에 겹치지 않게 해서 넣어준다.

 

count = 0 으로 해주고

for 문을 돌려서 lst에 s를 포함하고 있으면 배운 글자로 읽을 수 있으니깐

count를 올려주고 res 에 최댓값을 저장해둔다.

 

 

정답 코드 이 문제는 시간초과땜에 미친싸움을 한 문제다. 

from itertools import combinations
import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

N, K = map(int,input().split(" "))


word = {"a","t","i","c","n"}
candidate = set(chr(i) for i in range(97, 123)) - word
words = [sys.stdin.readline().rstrip() for _ in range(N)]
remain_sets = [set(w) - word for w in words]
if K < 5:
    print(0)
else:
    res = 0
    for i in combinations(candidate,K-5):
        lst = set(i)
        count = 0
        for s in remain_sets:
            if lst.issuperset(s): # lst가 s를 가지고있냐
                count += 1
        res = max(count,res)

    print(res)