빙산 [백준 1062] - python

 

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

def BOJ1062() :
  def replace_antatica(words) :
    words = words.replace('a', '')
    words = words.replace('n', '')
    words = words.replace('t', '')
    words = words.replace('i', '')
    words = words.replace('c', '')

    return words

  N, K = map(int, input().split())
  words = []
  for _ in range(N) :
    words.append(input().strip())
  
  if K < 5 :
    print(0)
    return

  alphabet = set();
  
  for word in words :
    for i in word :
      alphabet.add(i)
  
  replaced_words = []
  for word in words :
    replaced_words.append(replace_antatica(word))

  words_without_prefix = list(filter(lambda x : x not in list('antatica'), alphabet))

  if len(words_without_prefix) == 0 :
    print(N)
    return 

  word_combinations = combinations(words_without_prefix, min(K - 5, len(words_without_prefix)))

  max_words = 0
  for combination in list(word_combinations) :
    count = 0
    for word in replaced_words :
      for i in combination : 
        word = word.replace(i, '')
      if not word :
        count += 1
    max_words = max(max_words, count)

  print(max_words)

BOJ1062()

 

풀이 방식 

1. 탈락하는 케이스 부터 먼저 걸러주었다. 배우는 단어의 개수가 5개 미만일 경우에는 단어를 배울수가 없다.

2. antic를 포함해서 고유 철자를 먼저 빼주었다. 

3. 고유 철자중 배울수 있는 개수를 선택하여 조합을 돌려주었고 모든 케이스의 경우에 배울수 있는 것들중 최댓값을 구하였다.

 

 

위의 코드 방식은 너무 오래걸린다. 불필요한 로직도 군데군데 보인다.

다른 분들의 코드를 보니까 비트마스크를 많이 이용하였다.

일주일 뒤에 풀때는 비트마스크를 한번 적용해서 더 나은 코드로 발전시켜보아야 겠다.

 

 

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

1062번: 가르침