[백준] 1062번 가르침 파이썬 풀이

이번에는 백트래킹 골드4문제인 1062번 가르침을 어떻게 해결하였는지를 작성하는 시간을 가져보도록 하겠습니다.

 

정답풀이

import sys

n, k = map(int, input().split())

# k 가 5보다 작으면 어떤 언어도 배울 수 없음
if k < 5:
    print(0)
    exit()
# k 가 26이면 모든 언어를 배울 수 있음
elif k == 26:
    print(n)
    exit()

answer = 0
words = [set(sys.stdin.readline().rstrip()) for _ in range(n)]
learn = [0] * 26

# 적어도 언어 하나는 배우기위해 a,c,i,n,t 는 무조건 배워야함
for c in ('a', 'c', 'i', 'n', 't'):
    learn[ord(c) - ord('a')] = 1

def dfs(idx, cnt):
    global answer

    if cnt == k - 5:
        readcnt = 0
        for word in words:
            check = True
            for w in word:
                if not learn[ord(w) - ord('a')]:
                    check = False
                    break
            if check:
                readcnt += 1
        answer = max(answer, readcnt)
        return

    for i in range(idx, 26):
        if not learn[i]:
            learn[i] = True
            dfs(i, cnt + 1)
            learn[i] = False


dfs(0, 0)
print(answer)

 

틀린풀이

# 가르침
# 복습 횟수:0, 01:30:00, 복습필요O
import sys
si = sys.stdin.readline
N, K = map(int, si().split())
tmp = [list(map(str, si().strip())) for _ in range(N)]
string_set = list()
word = {'a', 'n', 't', 'i', 'c'}

for string in tmp:
    string_set.append(string[4:-4])

answer = 0
# a n t i c
using_word = dict()
for string in string_set:
    for s in string:
        if s == 'a' or s == 'n' or s == 't' or s == 'i' or s == 'c': continue

        using_word[s] = 1

def dfs(index, word: set):
    global answer
    if index == K - 5:
        tmp = 0
        for string in string_set:
            isTrue = True 
            for s in string:
                if s not in word:
                    isTrue = False
                    break
            if isTrue:
                tmp += 1
        answer = max(answer, tmp)
        return
    
    for key, val in using_word.items():
        if using_word[key]:

            word.add(key)
            using_word[key] = 0
            
            dfs(index + 1, word)
            
            word.remove(key)
            using_word[key] = 1

dfs(0, word)
print(answer)

 

1. DFS 횟수는 시간 초과 풀이가 훨씬 적은데 시간초과가 나는 이유를 알지 못했습니다. 문자열 슬라이싱에 시간이 걸린다는 소리도 있어 최대한 뺴고 진행을 해보았지만 시간초과가 여전히 발생하였습니다.

그래서 질문을 했더니 "쓸데없이 무거운 자료구조를 사용했기 때문"이라고 들었습니다. 그차이 때문에 시간초과가 발생한것이었습니다. 또한 abc랑 bca랑 acb랑 cba랑 이런게 같은 건데 이걸 처리 안해서 순열이라 훨씬 많이 돌기 때문이라고 피드백을 받았습니다.