[백준(파이썬/Python)] 1062_가르침

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

1062번: 가르침

 

이 문제에서 'a','n','t','i','c'는 반드시 가르쳐야 하고, 모든 단어의 맨 처음 네 글자가 'anta', 'tica'라는 조건은 아마 시간 복잡도를 맞추기 위한 설정이거나 약간의 구현(?)을 유도하기 위한 것 같습니다.

 

하지만 기본적으로 단어의 개수나 알파벳의 수가 크지 않기 때문에 완전 탐색을 해야겠다는 생각을 할 수 있었고, 다만 조금이나마 효율적인 완전탐색을 하기 위한 방법으로 set 자료구조와 learned라는 리스트를 이용했습니다.

 

learned 리스트는 약 150칸짜리 배열로, 문제에서 주어진 a부터 z까지 알파벳을 아스키코드표로 변환하면 이 배열 안에 표기할 수 있게 됩니다. 이를 이용해서 각 단어의 알파벳이 이 배열에 존재하는지 확인하는 방식으로 풀면 되겠다는 아이디어입니다.  

 

즉, 'a','n','t','i','c'는 반드시 가르쳐야 하기 때문에 K개에서 5개를 제외한 알파벳을 조합해보고, 이를 learned리스트에 True로 체크하고 단어를 몇 개 읽을 수 있는지 세보는 것이죠.

 

그리고 다시 learned리스트에서 이전 알파벳을 False로 바꿔보고 조합에서 다른 경우를 뽑아 True로 바꾸고 진행해봅니다.

이 과정을 반복하면서 배운 알파벳으로 읽을 수 있는 단어를 세서, 그 최대값을 구하면 됩니다.

 

[풀이]

from itertools import combinations as C
import sys

# 지금 배운 알파벳으로 몇 단어를 읽을 수 있는지 리턴하는 함수
def countReadableWords(words, learned):
    count = 0
    for word in words:
        canRead = True
        for w in word:
            # 배우지 않은 알파벳이 있다면 False
            if learned[ord(w)] == False:
                canRead = False
                break
        if canRead:
            count += 1
	return count

n, k = map(int, input().split())
answer = 0
alphabet = set(chr(i) for i in range(97, 123)) - {'a','n','t','i','c'}
words = [sys.stdin.readline().rstrip()[4:-4] for _ in range(n)]

if k >= 5:
    learned = [False] * (150)
    for x in {'a','n','t','i','c'}:
       learned[ord(x)] = True
	
    # 남은 알파벳 중에서 k-5개를 선택해본다.
    for teach in list(C(alphabet, k-5)):
        for t in teach:
            learned[ord(t)] = True
        count = countReadableWords(words, learned)
        if count > answer:
            answer = count
        # 배운 단어 초기화
        for t in teach:
            learned[ord(t)] = False
    print(answer)
else:
	print(0)