백준 1062 가르침

combination (조합) 을 이용해서 모든 경우의 수를 다 확인하는 방법으로 해결한 문제였다.

📜 문제 바로 가기 : 가르침

제출코드

import sys
input = sys.stdin.readline

def removeWord(word): # "anta", "tica" 제거
    n = len(word)
    return word[4:n-4]

def sortWord(word):
    lst = []
    for w in word:
        if w not in essential:
            lst.append(w)
    
    lst.sort()
    return "".join(lst)

def recur(s, last, word): # combination
    global ans

    if s == K:
        dict = makeMap(word)
        cnt = 0
        for s_word in wordList:
            for w in s_word:
                if dict[w] == 0:
                    break
            else:
                cnt += 1
        ans = max(ans, cnt)
        return
    
    for i in range(last+1, 21):
        recur(s+1, i, word+teaching[i])


def makeMap(word):
    dict = makeDefaultMap()
    for w in word:
        dict[w] = 1

    return dict

def makeDefaultMap():
    dict = {}
    for w in teaching:
        dict[w] = 0

    return dict

N, K = map(int, input().split())
essential = ["a", "n", "t", "i", "c"]

if K < 5: # a, n, t, i, c 5개는 꼭 필요
    print(0)
    exit()

K -= 5
wordList = []
for _ in range(N):
    word = sortWord(removeWord(input().rstrip()))
    wordList.append(word)

teaching = "bdefghjklmopqrsuvwxyz" # a, n, t, i, c를 제외한 21글자
ans = 0
recur(0, -1, "")

print(ans)

접근방법

주어지는 단어 50개였지만 알파벳이 필수 알파벳을 제외한 21개만 고려하면 됐기 때문에 조합으로 시간안에 해결된 문제였다. (빠르진 않았다.)

단어가 주어지면 "anta", "tica" 에 대한 처리를 해준 다음 리스트(wordList)에 저장하였고 재귀 함수(recur) 를 이용하여 조합을 구현했다. 그리고 하나의 조합된 그룹이 완성되면 그걸로 wordList 의 단어를 확인하면서 만들 수 있는 단어인지 체크하였다. 그 확인은 인덱싱이나 해시맵이 빠를것 같아서 dictionary 자료구조를 이용하였다.