[Algorithm] 백준 1062 : 가르침

문제
https://www.acmicpc.net/problem/1062
풀이
https://github.com/nowChae/algorithm/blob/master/%EB%B0%B1%EC%A4%80/Gold/1062.%E2%80%85%EA%B0%80%EB%A5%B4%EC%B9%A8/%EA%B0%80%EB%A5%B4%EC%B9%A8.py

combinations 모듈을 사용하지 않고 풀어보려고 했지만 도저히 안쓰고는 못 풀겠어서 사용했다. combinations 모듈도 생각보다 많이 사용하게 되는 것 같아서 다음번엔 이 라이브러리 사용법에 대해 좀 알아보고 정리해놔야겠다.

위의 생각대로 코드를 구현하여 python3로 돌렸을 때는 백준에서 시간초과가 나왔는데.. pypy3로 돌려서 겨우 넘어간 문제였다. 백트래킹을 이용해서 푸는 방식도 있던 데 다음 번엔 다른 방식으로 구현해서 python3으로도 돌아갈 수 있도록 시간을 줄여봐야겠다.

< 풀이 코드 >

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


N, K = map(int,input().split())
remain = K-5

study_need_word = []
study_need = []
for i in range(N):
    word = input()
    len_word = len(word)
    if (K < 5) and (i == N-1):
        print(0)
        break
    elif K >= 5:
        not_in = []
        for j in range(4,len_word-4):
            if (word[j] not in 'antic') and (word[j] not in not_in):
                not_in.append(word[j])
                if word[j] not in study_need:
                    study_need.append(word[j])
        
        if len(not_in) <= remain:
            study_need_word.append(not_in)
            print(not_in)
print(study_need)
print(study_need_word)
if remain >= 0:
    combi_list = map(''.join,combinations(study_need, remain))
        
    result = []
    for combi in combi_list:
        count = 0
        for word in study_need_word:
            is_can_read = True
            for w in word:
                if w not in combi:
                    is_can_read = False
            
            if is_can_read:
                count += 1
        result.append(count)

    if result:
        print(max(result))
    else:
        print(N)