오늘은 다른 분의 풀이를 분석해보겠어요 ~~~!~

1. 내 풀이 - 시간초과

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

n, k = map(int, input().split())
words = list()
char = set()
for _ in range(n):
    word = input().rstrip()
    words.append(word[4:-4])
    for i in word[4:-4]:
        char.add(i)

char = list(char)
already = ['a', 't', 'n', 'i', 'c']

k -= 5
if k <= 0:
    print(0)

else:
    answer = n
    maxCount = 0 
    for comb in combinations(char, k):
        candidate = set(already)
        for i in comb:
            candidate.add(i)
        answer = n
        minCount = 0
        for word in words:
            for i in word:
                if i not in candidate:
                    answer -= 1
                    break
        maxCount = max(maxCount, answer)
    print(maxCount)

시간 초과 났던 풀이 ... ㅠㅠ 여기저기 for문도 많고 for문 속 if문도 많아서 그런 듯 하다. 그런데 도저히 고쳐야할 곳이 없어서 못 고쳤던 풀이.

2. 다른 풀이

import sys

n, k = map(int, input().split())

# k 가 5보다 작으면 어떤 언어도 배울 수 없음
if k < 5:
    print(0)
    exit()
# k 가 26이면 모든 언어를 배울 수 있음
elif k == 26:
    print(n)
    exit()

answer = 0
words = [set(sys.stdin.readline().rstrip()) for _ in range(n)]
learn = [0] * 26

# 적어도 언어 하나는 배우기위해 a,c,i,n,t 는 무조건 배워야함
for c in ('a', 'c', 'i', 'n', 't'):
    learn[ord(c) - ord('a')] = 1


def dfs(idx, cnt):
    global answer

    if cnt == k - 5:
        readcnt = 0
        for word in words:
            check = True
            for w in word:
                if not learn[ord(w) - ord('a')]:
                    check = False
                    break
            if check:
                readcnt += 1
        answer = max(answer, readcnt)
        return

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

dfs(0, 0)
print(answer)

풀이 출처: https://kyun2da.github.io/2020/09/26/teaching/

일단 예외 케이스부터 생각했다. 5 이하와 모든 알파벳을 다 배울 수 있는 경우! 이런 예외 케이스를 먼저 생각해두는 것도 중요한 듯하다.

그 후에는 정답으로 출력할 answer 변수와 배운 알파벳을 체크할 learn 배열을 일단 0으로 초기화 해준다. ➡️ 이것이 바로 비트 마스킹 ❗️

그리고 입력을 받은 후에, 모든 단어에 들어가는 'anta'와 'tica'에 해당하는 'a, c, i, n, t'는 무슨 일이 있어도 배우므로 이에 해당하는 learn 인덱스를 1로 바꾸어준다.

그 후에는 dfs(idx, cnt) 함수를 통해 들어온 단어들을 체크해주게 되는데, if문을 보기 전에 for문부터 살펴보자.

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

여기서 제일 처음 들어가는 idx 는 idx = 0로, a부터 탐색을 시작하게 된다. 우리는 어떤 알파벳을 배웠을 때 그 알파벳을 포함하여 계속해서 배운 알파벳만을 탐색해야 한다. 그렇기 때문에 if not 절을 사용하여 learn[i] 알파벳을 배우지 않았을 때 (0이어야만 not에 의해 if문이 참이 되므로) 를 먼저 찾아야 한다.

그 후에 그 알파벳을 배웠다고 하고 (learn[i] = True), 그 알파벳에서 분기하여 다음 알파벳을 배우러 떠나는 것이다.

자 그럼 이제 함수의 if문을 살펴보자.

if cnt == k - 5:
    readcnt = 0
    for word in words:
        check = True
        for w in word:
            if not learn[ord(w) - ord('a')]:
                check = False
                break
        if check:
            readcnt += 1
    answer = max(answer, readcnt)
    return

cnt == k-5 는 배울 수 있는 알파벳 k개에서 꼭 배워야하는 'a, n, t, i, c'를 제외한 알파벳 수와 지금까지 배운 알파벳의 수 (cnt)가 동일해졌을 때에 해당한다. 여기에 걸리면 배울 수 있는 모든 알파벳 개수를 다 배웠다는 뜻이다.

readcnt는 지금까지 배운 알파벳으로 익힐 수 있는 단어의 개수이다. 아래에서 차차 살펴보도록 하자.

이제는 제시된 단어를 모두 알아먹을 수 있는가를 체크해야 한다. words 꾸러미에서 하나씩 단어를 꺼낸다. 여기서 check 변수는 배울 수 있는 단어인지의 그 여부를 나타낸다. 그 이유는 두 번째 for문을 살펴보면 알 수 있는데, 두 번째 for문은 단어 속의 글자 하나씩을 확인하면서 그 알파벳을 배웠는지 확인을 하는 코드이다.

만약 그 알파벳을 배우지 않았다면, 우리는 이 단어를 익힐 수 없으므로 더 이상 그 단어를 확인할 필요가 없으므로, 배울 수 있는 단어를 나타내는 변수인 check = False 로 설정 해준 뒤, break를 통해 단어의 알파벳을 확인하는 for문을 빠져나와준다.

그 후에는 만약 check가 True면, 즉 익힐 수 있는 단어라고 판단되면 실행되는 if문이다. 이 아래는 이해하기 쉬울테니 설명은 패스!

2-1. 비트 마스킹이란? 🧐

위에서 등장한 비트 마스킹. 풀이를 보며 감이 왔겠지만 좀 더 알아보자.

비트 마스킹 (Bit masking) 자체는 정수의 이진수 표현을 자료구조로 사용하는 기법이다. 지금처럼 0 혹은 1로 초기화 한 후 어떠한 조건에 따라 이를 바꾸어 주는 것 역시 일종의 비트 마스킹 기법으로 쓰이는 것 같다.

일단 이 풀이에서는 이 방법과 인덱스를 통해 곧바로 알파벳에 접근할 수 있었으니 시간 효율면에서 큰 이점을 본 것 같다.

3. 마치며

이렇게 다른 분의 풀이를 아주 꼼꼼하게 분석해보았다. 요즘 브루트포스 풀면서 느끼는 것은 백트래킹과 크게 다를 바가 없는 것이라는 거다. 그래도 브루트포스보다는 백트래킹이 아주 조금은 시간 복잡도가 덜한 것 같으니 실버 몇 문제 풀고 이제 슬슬 백트래킹으로 다시 넘어가봐야겠다.

+) 참고로 python3 말고 pypy3로 제출하면 위 풀이가 제대로 채점된다.