[BOJ] 1062 가르침 - python

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

1062번: 가르침

<- 최초 코드(시간초과) ->

import sys
from itertools import combinations

def input():
    return sys.stdin.readline().rstrip()

N, K = map(int, input().split())
word = [input() for _ in range(N)]

basic = {"a","n","t","i","c"} #무조건 배워야 하는 글자 수
learnNum = K - len(basic)
if learnNum < 0:
    print(0)
    exit()
if K == 26:
    print(N)
    exit()

wordSetList = []
for w in word:
    if len(set(list(w))-basic) > learnNum:
        continue
    else:
        wordSetList.append(set(list(w))-basic)

toLearn = set()
for wo in wordSetList:
    toLearn = toLearn | wo #합집합

if len(toLearn) <= learnNum: #무조건 다 배울 수 있음
    print(N)
    exit()

alphComb = combinations(toLearn,learnNum)

cntList = []
for comb in alphComb:
    cnt = 0
    for wordSet in wordSetList:
        if len(wordSet - set(comb)) == 0:
            cnt += 1
    cntList.append(cnt)

print(max(cntList))

<- 최종 CODE ->

import sys
from itertools import combinations

def input():
    return sys.stdin.readline().rstrip()

candidates = ['b','d','e','f','g','h','j','k','l','m','o','p','q','r','s'
							,'u','v','w','x','y','z'] #총 21개
must = {'a','n','t','i','c'}

N, K = map(int, input().split())
input_word = [input() for _ in range(N)]
#print("word",word,N,K)

word = []
for i in range(N):
    word.append(list(set(input_word[i]) - must))


bit_word = [0] * N
for i, W in enumerate(word):
    for w in W:
        bit_word[i] |= 1 << ord(w) - ord('a') 
#해당하는 각 비트에 1 세팅 #1이 하나라도 존재하면 1로 세팅

if K < 5:
    print(0)
elif K == 26:
    print(N)
else:
    #combination사용
    #가능한 k-5개의 알파벳들의 조합을 구하려면 2의 n승들의 집합에서 k-5개를 뽑은 후 sum 시킨 애를 구하면 됨
    power_of_2 = [2 ** i for i in range(26)]
    max_count = 0

    for comb in combinations(power_of_2 , K-5):
        current = sum(comb)
        count = 0
        for bit in bit_word:
            #test가 얼마나 만족하는지 확인
            if bit & current == bit:
                count += 1
        if count > max_count:
            max_count = count
    print(max_count)

• 참고

[Python] 백준 - 1062 가르침

[Python] 백준 - 1062 가르침

• 풀이 방법

  1. 읽어야 하는 단어들을 입력 받은 후, mus로 읽어야 하는 a,n,t,i,c를 제외한 알파벳들을 set을 이용하여 word로 만든다.  2. 총 알파벳들은 26개가 있는데 **int형의 경우 2의 31승까지** 표현 가능하므로 모든 알파벳들을 이용한 1111...11 (abcd...yz) 도 표현 가능하다. 3. 각 word들을 2진수로 변환한다.  4. k가 5보다 작을 경우 하나도 읽을 수 없으므로 종료, 26일 경우 모두 읽을 수 있으므로 n개를 프린트한다 5. 그 외의 경우 가능한 알파벳들의 k-5개 조합들을 모두 word에 테스트해보고 max_num인 경우를 프린트한다.           ⇒ 가능한 알파벳들의 k-5개 조합은 어떻게 구할까?          각 알파벳들은 2**0,2**1,2**2 ... 2**n으로 구성되어 있으므로 2**0 에서 2**25까지의 숫자들 중에서 k-5개를 뽑은 후 그것들을 더하면 해당 수가 된다.      6. word에 테스트를 할 때는 word와 test를 &시켜 word가 나오면 통과이다.           w t  결과          0 0  0 #안배워도되는것, 없음 → 0 정상          0 1  0 #안배워도되는것, 있음 → 0 정상          1 0  0 #배워야하는것, 없음 → 0 정상          1 1  1  #배워야하는것, 있음 → 1 정상

얻어가는 것

• 완전탐색에서 비트마스크 사용

완전탐색 - 비트마스크 기초

• 완전 탐색 : 모든 경우의 수를 다 해보기!
  • 순열,조합 사용
  • 재귀함수 사용
  • 비트마스킹 사용
  • 백트래킹 사용
  • bfs 사용
• 비트마스킹 

  

  

• n진수 변환
• : 1을 left shift(<<) 하여 n진수로 변환한다.
  • << left shift ( bit * 2의 n승)
  • right shift ( bit // 2의 n승)

#2진수로 변환
bit |= 1 << 2

#3진수로 변환
bit |= 1 << 3

#n진수로 변환
bit |= 1 << n

• 2의 n승

power_of_2 = [2**i for i in range(26)]

느낀점

"210921"

소요 시간 : 12D 이상

• 완전 탐색에서 itertools의 combination을 사용하면 되는데,
• set을 사용하게 되면 시간 초과 문제가 발생한다.
• bit-masking을 통해 시간 초과 문제를 해결한다.
• 그리고 풀리지 않으면 꼭... 다른 풀이를 보자...얻어가는 것