[백준] 1062번(가르침)

백준 1062번

✔️ 문제 풀이

처음 제출한 코드

import sys

input = sys.stdin.readline

word_list = []

start = 4
end = -4
words, n = map(int, input().split())

for i in range(words):
  word_list.append(input().rstrip())

# 아래의 다섯개 알파벳은 무조건 가르쳐야함
essential = {'a', 'c', 'i', 'n', 't'}

# 알파벳 존재여부 체크할 리스트 생성
alphabet = [0] * 26
check_list = set(_ for _ in range(26))

for alpha in essential:
  alphabet[ord(alpha) - ord('a')] = 1
  check_list.discard(ord(alpha) - ord('a'))

check_list = list(check_list)

# 생성된 알파벳 조합으로 단어를 읽는 것이 가능한지 검사
# dfs에서 호출
def check():
  count = 0
  
  for word in word_list:
    for cha in word[start:end]:
      if alphabet[ord(cha)-ord('a')] == 0:
        break
    else:
      count += 1
      
  return count

stack = []
result = 0

# 알파벳 조합 생성
def dfs(index):

  global result
  
  if len(stack) == n-5:
    result = max(result, check())
    return

  for i in range(index, len(check_list)):
    if not alphabet[check_list[i]]:
      stack.append(i)
      alphabet[check_list[i]] = 1
      dfs(i + 1)
      stack.pop()
      alphabet[check_list[i]] = 0

if n < 5:
  print(0)
else:
  dfs(0)
  print(result)

◾ 알파벳 리스트를 활용하여 문제 풀이

• a, c, i, t, n 5개의 알파벳은 무조건 가르쳐야함
  ⇒ 따라서 가르치는 알파벳의 개수가 5개보다 작으면 0을 return
• dfs를 이용하여 k-5개의 알파벳 조합을 생성
  ◽ stack의 길이가 k-5와 같아지면 입력된 단어들을 읽을 수 있는지 검사하는 check 함수 호출
  ◽ check 함수에서는 word[4:-4]에 속하는 알파벳을 숫자로 변환하여 alphabet 리스트에서 1의 값을 갖는지 검사한다

◾ 결과

• Python3에서는 시간초과. PyPy3에서만 통과함

✔️ 다른 풀이

• 다른 풀이를 검색해보니 비트마스킹을 활용하면 더 빠른 시간 내에 문제풀이 가능
• 이 방식으로 작성한 코드는 Python3으로도 통과된다

◾ 비트마스킹을 활용한 풀이

• 알파벳을 비트 자리수로 표현
  ex) a는 0b1, b는 0b10, c는 0b100
• 이를 위해 left shift 연산을 이용하여 1을 0~26만큼 이동시킨 값을 alphabet 리스트에 저장한다.
• 가르친 알파벳을 2진수 숫자로 변환한 값과 단어를 2진수 숫자로 변환한 값에 & 연산을 하면 두 값 모두에 속한 알파벳의 자리수만 1을 갖는다
• 즉, 연산 결과가 단어를 2진수 숫자로 변환한 값과 일치하면 그 단어는 읽을 수 있는 단어이다

최종 제출 코드

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

n, k = map(int, input().split())
words = []

if k < 5: print(0)
  
else:
  
  learned = 0
  
  for cha in 'acint':
    learned = learned | (1 << (ord(cha) - ord('a')))
    
  # 1, 2, 3 => 1(0b1), 2(0b10), 4(0b100)의 형태로 변환해서 저장 
  alphabet = [1 << c for c in range(26) if chr(c+97) not in 'acint']
  
  for i in range(n):
    word = input().rstrip()
    bit = 0
    for cha in word:
      bit = bit | (1 << ord(cha) - 97)
    words.append(bit)
  
  
  result = 0
  
  
  for comb in combinations(alphabet, k-5):
    count = 0
    know_bit = sum(comb) | learned
    for word in words:
      if word & know_bit == word:
        count += 1
    result = max(result, count)
  
  print(result)