[백준] 1062 : 가르침 / python

1. 문제 설명

1062번: 가르침

 

남극에 사는 김지민 선생님은 학생들이 되도록이면 많은 단어를 읽을 수 있도록 하려고 한다.

그러나 지구온난화로 인해 얼음이 녹아서 곧 학교가 무너지기 때문에,

김지민은 K개의 글자를 가르칠 시간 밖에 없다.

김지민이 가르치고 난 후에는, 학생들은 그 K개의 글자로만 이루어진 단어만을 읽을 수 있다.

김지민은 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지 고민에 빠졌다.

남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다.

남극언어에 단어는 N개 밖에 없다고 가정한다.

학생들이 읽을 수 있는 단어의 최댓값을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 단어의 개수 N과 K가 주어진다.

N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다.

둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다.

단어는 영어 소문자로만 이루어져 있고, 길이가 8보다 크거나 같고, 15보다 작거나 같다.

모든 단어는 중복되지 않는다.

 

출력

첫째 줄에 김지민이 K개의 글자를 가르칠 때, 학생들이 읽을 수 있는 단어 개수의 최댓값을 출력한다.

 

2. 풀이 전 계획과 생각

먼저, 완전 탐색으로 접근해보자.

 

첫번째 입력

N = 3 K = 6

antarctica

antahellotica

antacartica

 

읽을 수 있는 단어를 뽑을 때, a, n, t, i, c를 포함해야 하며, anta, tica는 체크 안해줘도 된다.

K가 만약에 5미만이면 0을 출력해준다.

voca[4:-4]만 체크해주면 된다. 뽑은 단어 갯수 외에 단어가 존재하는지 체크하면 된다.

 

단어가 존재하는지 존재하지 않은지 체크는 어떻게 해줄까?

if voca[i] in (뽑은 단어 저장한 자료구조)

 

시간 안에 풀 수 있는지, 경우의 수를 따져보자.

 

R = K-5

 

5글자를 제외한 21개중에서 R개 글자를 뽑는 최대 경우의 수
→  R = 10 일 때, 21C10 = 352716

 

K개 뽑은 case마다
단어들을 읽을 수 있는지 체크한다. (체크할 범위의 길이는 0~7이다.)

최대 단어의 갯수 50이다.
시간 복잡도를 줄이기 위해, 리스트 대신 해쉬테이블을 사용해주자. O(1)

→ 최악의 시간 복잡도는 352716 * 7 * 50 > 1.2억이다.

 

읽을 수 있는 단어의 최댓값을 갱신한다.

 

3. 풀이 

from itertools import combinations

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

alphabet = [chr(n + 97) for n in range(0, 26)]
alphabet.remove('a')
alphabet.remove('c')
alphabet.remove('i')
alphabet.remove('n')
alphabet.remove('t')

max_word_num = 0

def get_word_num(case):
    dict = {'a': 1, 'c': 1, 'i': 1, 'n': 1, 't': 1}
    count = 0

    for select_word in case:
        dict[select_word] = 1
    for word in words:
        is_readable = True
        check_words = word[4:-4]
        for check_word in check_words:
            if check_word not in dict:
                is_readable = False
        if is_readable:
            count += 1
    return count

if K < 5:
    print(0)
else:
    cases = list(combinations(alphabet, K - 5))
    for case in cases:
        max_word_num = max(get_word_num(case), max_word_num)
    print(max_word_num)

 

pypy3로 돌리면, 시간 안에 문제 해결

 

4. 풀이 후 알게된 개념과 소감

• 실수 주의! 초기화 해야 할 범위를 잘 체크해주자.
  • case마다 해쉬테이블을 초기화 해줘야 한다. (초기화해주지 않았다.)
  • word마다 is_readable 초기화 해줘야 한다. (더 큰 범위인 case마다 초기화 해주었다.)

 

5. 풀이하면서 막혔던 점과 고민

🤔  다른 방법으로도 풀 수 있을까?

→ 재귀로 접근해볼까?

a, b, c, ... , x, y, z O O O ... X X X ... a, n, t, i, c를 제외하고 O, X를 따진다.

1. 26-4개의 알파벳 중에서 K-5개를 고름
2. 각각의 단어에 대해서 3)배운 알파벳으로만 이루어져 있는지 검사

26-5개 중에서 K-5개를 고르는 것을 재귀를 사용하여 구현하면, 시간복잡도는? 2^21 = 2,000,000

앗 조합보다 더 많이 나온다. 😛 → 시간 초과

def count(words):
    cnt = 0
    for word in words:
        ok = True
        for x in word:
            if not learn[ord(x)-ord('a')]:
                ok = False
                break
        if ok:
            cnt += 1
    return cnt

def go(index, k, words):
    if k < 0:
        return 0
    if index == 26:
        return count(words)
    ans = 0
    learn[index] = True
    t1 = go(index+1, k-1, words)
    learn[index] = False
    if ans < t1:
        ans = t1
    if index not in [ord('a')-ord('a'), ord('n')-ord('a'), ord('t')-ord('a'), ord('i')-ord('a'), ord('c')-ord('a')]:
        t2 = go(index+1, k, words)
        if ans < t2:
            ans = t2
    return ans

n,m = map(int,input().split())
words = [input() for _ in range(n)]
learn = [False] * 26
print(go(0,m,words))

 

6. 풀이하면서 막혔던 점과 고민

효율적인 방법을 검색해보니, 비트마스크 방법을 찾을 수 있었다.

각각의 단어가 배운 알파벳으로만 이루어져 있는지 검사할 때 시간을 줄여줄 수가 있다.

얼만큼 줄여줄 수 있을까? O (단어의 개수 X 각 단어의 길이) → O (단어의 개수)

실제로 그 단어가 무엇인지가 중요한 것이 아니다.

그 단어에 알파벳이 어떤 순서로 이루어져 있는 것이 중요한 것이 아니다.

각 단어에 속해있는 알파벳이 무엇인지만 중요하다.

→ 각 단어를 비트마스크로 나타낼 수 있다.

 

7. 다른 풀이 - 비트마스크

def count(mask, words):
    cnt = 0
    for word in words:
        if (word & ((1<<26)-1-mask)) == 0:
            cnt += 1
    return cnt
def go(index, k, mask, words):
    if k < 0:
        return 0
    if index == 26:
        return count(mask, words)
    ans = 0
    t1 = go(index+1, k-1, mask | (1<<index), words)
    if ans < t1:
        ans = t1
    if index not in [ord('a')-ord('a'), ord('n')-ord('a'), ord('t')-ord('a'), ord('i')-ord('a'), ord('c')-ord('a')]:
        t2 = go(index+1, k, mask, words)
        if ans < t2:
            ans = t2
    return ans

n,m = map(int,input().split())
words = [0] * n
for i in range(n):
    s = input()
    for x in s:
        words[i] |= (1 << (ord(x)-ord('a')))
print(go(0,m,0,words))