1062: 가르침

풀이 시간

• 43m
• 처음에 brute force로 코드를 짰는데 메모리 초과가 나서 알고리즘 분류를 보고 비트마스킹 + 백트래킹 알고리즘을 사용하여 다시 풀었다
• 비트마스킹 개념은 구글링을 통해 아이디어를 참고했다

구현 방식

• alphabet을 길이가 26인 리스트로 선언하여 index 별로 (알파벳 별로) 배웠다면 True, 배우지 않았다면 False로 처리해주었다 (비트마스킹 비슷한 개념)

• 남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝나기 때문에 그 부분은 미리 alphabet 리스트에서 'a', 'n', 't', 'i', 'c'를 True로 처리해주었고, word를 입력받을 때도 마찬가지로 word = word[4:-4]로 미리 앞뒤를 제거해주었다

backtracking 구현

• max_word(학생들이 읽을 수 있는 단어 개수의 최댓값)은 backtracking을 통해 구해주었다

• 알파벳의 인덱스(idx)와 learn(dfs의 depth)를 input parameter로 설정함

for i in range(idx, 26):
    if not alphabet[i]:
        alphabet[i] = True
        dfs(i, learn + 1)
        alphabet[i] = False

• 위의 코드처럼 가르치고자하는 알파벳을 선택하는 부분을 구현해주었다

• max_word 갱신 조건은 depth(learn)이 K-5일 때이다 (끝나고 return은 필수)

메모리초과 코드

import sys

def combination(arr, n):
    result = []
    if n > len(arr):
        return result
    if n == 1:
        for i in arr:
            result.append([i])
    elif n > 1:
        for i in range(len(arr) - n + 1):
            for j in combination(arr[i+1:], n-1):
                result.append([arr[i]] + j)
    return result

def solution(di):
    global max_word

    local_max_word = 0
    for word in words:
        cnt = 0
        for w in word:
            if w not in di:
                break
            cnt += 1
        if cnt == len(word):
            local_max_word += 1
    
    max_word = max(max_word, local_max_word)

N, K = map(int, sys.stdin.readline()[:-1].split())

if K < 5: print(0); exit()
elif K == 26: print(N); exit()

words = []; alphabet = set()
for n in range(N):
    tmp = sys.stdin.readline()[:-1]
    tmp = tmp[4:-4]
    for t in tmp:
        if t not in alphabet:
            alphabet.add(t)
    words.append(tmp)

alphabet = list(alphabet)
combs = combination(alphabet, K - 5)

max_word = 0
for comb in combs:
    comb = comb + ['a', 'n', 't', 'i', 'c']
    solution(set(comb))
print(max_word)

• 가르치는 글자를 선택하는 모든 조합을 구하고 brute force로 이 조합을 순회하여 max_word를 갱신해주려고 했었다
• 그러나 combination을 구하는 과정에서 메모리초과가 발생함

최종 코드

import sys


def dfs(idx, learn):
    global max_word

    if learn == K-5:
        local_max_word = 0

        for word in words:
            flag = True
            for w in word:
                if not alphabet[ord(w) - ord('a')]:
                    flag = False; break
            if flag:
                local_max_word += 1

        max_word = max(max_word, local_max_word)
        return

    for i in range(idx, 26):
        if not alphabet[i]:
            alphabet[i] = True
            dfs(i, learn + 1)
            alphabet[i] = False

N, K = map(int, sys.stdin.readline()[:-1].split())

if K < 5: print(0); exit()
elif K == 26: print(N); exit()

words = []; alphabet = [False] * 26
for n in range(N):
    tmp = sys.stdin.readline()[:-1]
    tmp = tmp[4:-4]
    words.append(tmp)

for a in ['a', 'n', 't', 'i', 'c']:
    alphabet[ord(a) - ord('a')] = True

max_word = 0
dfs(0, 0)
print(max_word)

결과