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

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

1062번: 가르침

• 이 문제는 처음에 풀었을 때 시간 초과가 계속해서 발생했던 문제이다.
• anta와 tica를 만들수있는 알파벳 a, n, t, i, c를 제외한 알파벳 소문자 중에서 주어진 k 개수에서 5를 제외해서 경우의 수를 모두 구한 다음, 경우의 수로 나머지 알파벳을 만들 수 있는지에 대한 문제인데 이 부분을 구현할 때 시간 초과가 계속 발생했다.
• 해결방법은 0으로 초기화한 알파벳 체크리스트를 만들어주고 만약에 방문했으면 1로 변경해서 가능한지 가능하지 않은지에 대한 판단을 해줬다.
• 판단을 해주고, 1로 변경했던 리스트를 다음 경우의 수를 판단할 때 사용하기 위해 0으로 다시 바꿔주도록 백트래킹을 사용했다.

from itertools import combinations 
import sys
n, k = map(int, input().split())
answer = 0
# a,n,t,i,c는 반드시 가르쳐야 함

first_word = {'a','n','t','i','c'}

remain_alphabet = set(chr(i) for i in range(97, 123)) - first_word
data = [sys.stdin.readline().rstrip()[4:-4] for _ in range(n)]

def countReadableWords(data, learned):
   cnt = 0
   for word in data:
      canRead = 1
      for w in word:
          # 안배웠으니까 못읽는다.
         if learned[ord(w)] == 0:
            canRead = 0
            break
      if canRead == 1:
         cnt += 1
   return cnt

if k >= 5:
   learned = [0] * 123
   for x in first_word:
      learned[ord(x)] = 1

   # 남은 알파벳 중에서 k-5개를 선택해본다.
   for teach in list(combinations(remain_alphabet, k-5)):
      for t in teach:
         learned[ord(t)] = 1
      cnt = countReadableWords(data, learned)

      if cnt > answer:
         answer = cnt
      for t in teach:
         learned[ord(t)] = 0
   print(answer)
else:
   print(0)

 

아래는 계속 시간초과가 발생했던 코드이다.

 

 

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

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

first_word = {'a','n','t','i','c'}


# a,n,t,i,c 를제외한 알파벳들 리스트
remain_word = set(chr(i) for i in range(97, 123)) - first_word
data = [set(input().rstrip()[4:-4])-first_word for _ in range(n)]

result = 0
# 5보다 작으면 anta, tica를 만들수 없으므로 0개
if k < 5:
    print(0)
else:
    for i in list(combinations(remain_word,k-5)):
        ans = 0
        for data in data:
            if not set(words) - set(i):
                ans += 1
        if result < ans:
            result = ans
    print(result)