백준 1062 가르침 파이썬 풀이

1차시도

import sys
from collections import defaultdict
input = sys.stdin.readline
 
def main():
    N, K = map(int,input().split())
    if K < 5 : 
        print(0)
        return
 
    alphaCheck = 0    
    wordList = []
 
    for _ in range(N):
        word = input().rstrip()
        wordList.append(word)
        wordSet = set(list(word))
 
        for w in wordSet:
            alphaCheck |= 1<< ord(w) - ord('a')
 
    # a, c, i, n t 빼준다.
    defaultLetters = ['a','c','i','n','t']
    for d in defaultLetters :     
        alphaCheck &= ~(1<<(ord(d)-ord('a')))
    # 기본 5개 뺀 비트마스킹 문자열    
    alphaCheckString=bin(alphaCheck)[2:]
    # rokhe
 
    answer = 0
    accumSet = set(defaultLetters)    
 
    def backTrack(idx):
 
        if (idx>=len(alphaCheckString)):return
 
 
        # 추가 없이 계속
        backTrack(idx+1)
 
        # 추가하는경우
        if int(alphaCheckString[idx]):   
            accumSet.add(chr(len(alphaCheckString)-1-idx+97))
        nonlocal answer
        if len(accumSet)== K-5:
            temp=0
            print('accumSet',accumSet)
            for word in wordList:
                print('word',word)
                flag = True
                for w in set(list(word)):
                    if w in accumSet:
                        print(w,'True')
                        continue
                    else:
                        flag=False
                        print(w,'False')
                        break
                if (flag):
                    temp+=1
 
                answer = max(answer,temp)
 
        backTrack(idx+1)
 
 
        if int(alphaCheckString[idx]):
            # 제거
            accumSet.remove(chr(len(alphaCheckString)-1-idx+97))
 
    backTrack(0)
    print(answer)
    return
 
main()

정답1(블로그펌) -> 사실 정답이 아니었던 것임;; 타임아웃

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)

• 비트마스킹 안 써도 된다.
• learn 배열을 순회하면서, 새로 올리는 비트의 수가 총 k -5개가 되면 탈출하도록 재귀 코드를 짠다.
• for 문으로 인덱스를 순회하고, 인덱스랑 카운트를 매개변수로 가져간다. 매개변수가 전체 True개수가 아니라 내가 새로 만든 True개수라는 것이 중요한 부분이다.

수평이동 : for문으로 인덱스를 순회

수직이동 : 지금 인덱스부터 26까지 순회하면서

for 문 안에서 방문배열체크 - 재귀호출 - 방문배열 해제를 하면 수형도 수평이동을 할 수 있다.

2차시도

def main():
    ans = 0
    N,K = map(int,input().split())
    if K<5: 
        print(0)
        return 
    elif K==26:
        print(N)
        return
 
    words = []
 
    for _ in range(N):
        words.append(input())
 
    letters = ['a','c','i','n','t']
 
    learned = 0
    for l in letters :
        learned |= 1<<ord(l)-ord('a')
 
    # 단어 배우기
    def solution(i,x): # 시작인덱스, 앞으로 더 배워야 하는 단어 수
 
        nonlocal learned
        nonlocal ans
        if x == 0:
            tmpCnt = 0
            for w in words:
                flag = True
                for alpha in list(w):
                    if not learned & 1<<ord(alpha)-ord('a'):
                        flag=False
                        break
                if flag:
                    tmpCnt +=1
            ans = max(ans,tmpCnt)
            return #!!!리턴문 없어서 에러남
 
 
        # i인덱스가 밖으로 나가면 어쩌나 -> for문 때문에 그럴일없다.
        # x 가 0이 아닐 때 어쩌나 -> for문때문에 어차피 끝이 난다.
 
        for j in range(i,26): # i+1 아니고 i임
            if not learned & 1 << j: # 이 부분 굉장히 중요!!!
                learned |= 1<<j
                solution(j, x-1)
                learned &= ~(1<<j)
 
    solution(0,K-5)
    print(ans)
 
main()

• 타임아웃
• 정답인 줄 알고 복사해온게 정답이 아니어서.. 똑같이 타임아웃 나는 코드였는데 비트마스킹 때문에 그런지 알고 헤맸다.

정답

import sys
from itertools import combinations
input = sys.stdin.readline
 
def main():
    n,k = map(int, input().split())
    s = set([ord(a)-ord('a') for a in ['a','c','i','n','t']])
 
    learned = 0
    for i in s:
        learned |= (1<<i)
 
    words = [set(map(lambda x : ord(x)-ord('a'), input().strip())) for _ in range(n) ]
 
    def word2bit (word):
        res = 0
        for w in set(word):
            res|=1<<w
        return res
 
    bits = [word2bit(word) for word in words]
 
    candidates = set().union(*words)-s # 기본 5개를 제외한 알파벳집합
 
    answer = 0
    if k<5:
        print(0)
        return
    elif len(candidates) <= (k-5):
        print(n)
        return
    else:
        for c in combinations(candidates,k-5):
            tmp = learned
            for i in c:
                tmp |= (1<<i)
 
            tmp ^= (1<<26)-1 # 비트 반전. 안배운 게 1로 전부 변함
 
            answer = max(answer, sum(1 if (tmp & a) == 0 else 0 for a in bits))
 
        print(answer)
    return 
main()

• 이전 dfs풀이는 필요없는 알파벳을 모두 탐색하는데 그럴필요가 없다... 항상 생각하자. 시간초과 날 때는 필요없는 부분을 탐색하고 있지는 않은지!
• 마지막에 알고있는단어를 기준으로 읽을 수 있는 단어를 판단할 때, 비트간 포함여부가 성립하는지를 판단하는 로직이 중요하다.
  • 11101 을 알고 있고 00101을 읽어야 한다면 읽을 수 있다.
  • 앞의 비트를 뒤집고, 둘을 and해서 0이 나온다면 뒤 비트가 앞 비트에 포함된다는 걸 알 수 있다.