백준 1062 - 가르침 (파이썬)

문제

남극에 사는 김지민 선생님은 학생들이 되도록이면 많은 단어를 읽을 수 있도록 하려고 한다. 그러나 지구온난화로 인해 얼음이 녹아서 곧 학교가 무너지기 때문에, 김지민은 K개의 글자를 가르칠 시간 밖에 없다. 김지민이 가르치고 난 후에는, 학생들은 그 K개의 글자로만 이루어진 단어만을 읽을 수 있다. 김지민은 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지 고민에 빠졌다.

남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 남극언어에 단어는 N개 밖에 없다고 가정한다. 학생들이 읽을 수 있는 단어의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문자로만 이루어져 있고, 길이가 8보다 크거나 같고, 15보다 작거나 같다. 모든 단어는 중복되지 않는다.

출력

첫째 줄에 김지민이 K개의 글자를 가르칠 때, 학생들이 읽을 수 있는 단어 개수의 최댓값을 출력한다.

# 해결법

 

문제의 풀이나 답은 모두 맞는데 시간초과가 계속 떠서 이것저것 바꿔가며 시도해봤다.

strip이나 슬라이스로 저장하는 알파벳의 수를 최소화 시키기도 하고 input 대신 stdin.readline 도 써봤으나

계속해서 시간초과가 나왔다.

 

# 나의 코드

def read_func(cnt):
    global final_cnt
    if cnt == b - 5: # 알파벳을 다 배우면
        read_cnt = 0 # read_cnt = 0
        for word in alpha_list: # 입력받은 리스트를 돌면서
            for w in word: # 리스트의 한글자씩 돌면서
                if not learned[ord(w) - ord('a')]: # 글자를 안배웠다면
                    break # 멈춤
            else: # 모든 리스트를 배웠다면
                read_cnt += 1 # cnt + 1을 해줌
        final_cnt = max(final_cnt, read_cnt) # final_cnt는 둘 중 max 값으로 설정
        return
    for i in range(len(beta_list)): # beta_list의 길이만큼 반복
        if not learned[ord(beta_list[i]) - ord('a')]: # beta_list의 알파벳을 배우지 않았다면
            learned[ord(beta_list[i]) - ord('a')] = True # 배운것으로 바꾸고
            read_func(cnt + 1) # cnt를 + 1 하고 함수를 다시 호출
            learned[ord(beta_list[i]) - ord('a')] = False # 다시 안배운것으로 바꿈
a, b = map(int, input().split())
know_list = ['a','n','t','i','c'] # 무조건 배워야하는것
final_cnt = 0
learned = [False] * 26

for j in know_list: # a, n, t, i, c를 반복하면서
    learned[ord(j) - ord('a')] = True # 배운것으로 만들어준다
    
alpha_list = [set(input().lstrip('anta').rstrip('tica')) for _ in range(a)]
# anta, tica를 앞뒤에서 제거하고 alpha_list에 set으로 넣는다
# alpha_list = [set(input()[4:-4]) for _ in range(a)] strip을 써도 괜찮다.

beta_list = []
for k in range(len(alpha_list)): # alpha_list의 원소 수만큼 반복  
    beta_list.extend(alpha_list[k]) # beta_list에 괄호를 벗겨서 넣는다

beta_list = set(beta_list) # set으로 만들어서 중복을 없애고
beta_list = list(beta_list) # 다시 list로 만들어준다
if b < 5 or b == 26: # 배우는 알파벳이 5개 미만이거나 다 배운다면
    print(0 if b < 5 else a) # 5개 미만일 경우 0, 다 배울경우 a를 출력
    exit(0) # 바로 종료
else:
    read_func(0) # 함수 호출
    print(final_cnt)

 

# 개선 코드

 

def read_func(idx, cnt):
    global final_cnt
    if cnt == b - 5: # 알파벳을 다 배우면
        read_cnt = 0 # read_cnt = 0
        for word in alpha_list: # 입력받은 리스트를 돌면서
            for w in word: # 리스트의 한글자씩 돌면서
                if not learned[ord(w) - ord('a')]: # 글자를 안배웠다면
                    break # 멈춤
            else: # 모든 리스트를 배웠다면
                read_cnt += 1 # cnt + 1을 해줌
        final_cnt = max(final_cnt, read_cnt) # final_cnt는 둘 중 max 값으로 설정
        return

    for i in range(idx, 26): # 0부터 25까지 반복(learned[0]~[25] 값은 a~z까지 대응한다)
        if not learned[i]: # 배운적 없다면
            learned[i] = True # 배운것으로 바꾸고
            read_func(i, cnt+1) # cnt를 +1 하고 함수를 다시 호출
            learned[i] = False # 다시 안배운것으로 바꿈

a, b = map(int, input().split())
know_list = ['a','n','t','i','c'] # 무조건 배워야하는것
final_cnt = 0
learned = [False] * 26

for j in know_list: # a, n, t, i, c를 반복하면서
    learned[ord(j) - ord('a')] = True # 배운것으로 만들어준다

alpha_list = [set(input().lstrip('anta').rstrip('tica')) for _ in range(a)]
# anta, tica를 앞뒤에서 제거하고 alpha_list에 set으로 넣는다
# alpha_list = [set(input()[4:-4]) for _ in range(a)] strip을 써도 괜찮다.

if b < 5 or b == 26: # 배우는 알파벳이 5개 미만이거나 다 배운다면	 
    print(0 if b < 5 else a)  # 5개 미만일 경우 0, 다 배울경우 a를 출력
    exit(0) # 바로 종료
else:
    read_func(0, 0) # 함수 호출
    print(final_cnt)

이렇게 수정했을 때도 python으로 제출하면 시간초과가 나왔다. PyPy의 경우 정답으로 처리되었다.

흠... 시간복잡도에 대해서 더 공부할 필요가 있을 것 같다.

비트마스킹을 쓰는 방법도 있다고 하는데 그것도 공부해봐야겠다.