오랜만에 돌아온 알고리즘! 브루트포스 (#1062번 가르침)

오랜만에 백준 풀이로 돌아왔다.

이전에 백준을 풀었던 이유는, 소마에 합격하기 위해서였는데.

어느새 취준이 와버렸다....

 

이젠 취업을 위해서 푸는 백준. 정말 내 인생이 걸린 백준이다.

 

#1062번 가르침 https://www.acmicpc.net/problem/1062

1062번: 가르침

 

문제는 다소 복잡한 감이 있는데, anti로 시작하고 tica로 끝나는 단어가 N개 주어지면, K개의 알파벳을 추가로 학습하여 읽을 수 있는 단어의 최대 개수를 구하는 문제이다.

 

이 문제는 브루트포스 즉, 모든 경우의 수를 계산하는 방식으로 풀어야한다. 

 

그래서 자신있게 DFS로 해결했다.

 

틀린 코드

alphas = set(['a', 'n', 't', 'i', 'c'])

N, K = map(int, input().strip().split())

words = []
target = set()

for _ in range(N):
    t = [x for x in input()]

    # print(t)
    t = t[4:-4]
    # print(t)

    t = set(t)
    
    for i in alphas:
        t.discard(i)
    
    # print(t)
    words.append(t)

    for w in t:
        target.add(w)
target = list(target)
# print(words)
# print(target)

visited = [False for _ in range(len(target))]
answer = 0
def solve(words, target, visited, K):
    global answer
    if K == 0:
        # print(words)
        result = sum([1 if len(word) == 0 else 0 for word in words])
        # print(result)
        answer = max(answer, result)
        return result
    for i in range(len(target)):
        if not visited[i]:
            visited[i] = True
            t = target[i]
            new_words = []

            for word in words:
                tmp = set()
                for w in word:
                    if w != t:
                        tmp.add(w)
                new_words.append(tmp)

            solve(new_words, target, visited, K-1)
            visited[i] = False

K -= 5
if K:
    solve(words, target, visited, K)

print(answer)

 

하지만 역시나 시간초과가 났다.

 

다른 코드를 참고하여 파악한 시간 초과의 원인은 다음과 같다.

 

모든 단어의 알파벳을 set에 저장하고, 이 알파벳들을 기준으로 탐색한다.

탐색하는 과정에서, 각각의 단어에 탐색중인 알파벳을 제거하고 다음 알파벳 탐색으로 넘어간다.

 

-> 아무리 생각해도, 시간이 오래 걸릴 수 밖에 없다.

이를 획기적으로 단축시킬 수 있는 방법이 있는데, 바로 ascii코드를 기반으로 알파벳 리스트를 만드는 것이다.

-> 하단 코드의 learned_word 이다.

알파벳 set을 만들고 Visited 리스트 기반으로 탐색하는 과정을 leared_word 리스트 하나로 해결할 수 있다.

 

그리고, 읽을 수 있는 단어를 판단하는 과정을 배울 수 있는 최대 개수의 단어를 배운 상황에서만 진행함으로써 시간을 더욱 절약할 수 있다.

 

추가로 K가 5보다 작을 때, 26과 같을 때 처럼

무조건 오답, 무조건 정답인 경우를 별도로 처리해준다.

이렇게 하면 특정 테스트 케이스에 대한 탐색 시간을 줄일 수 있다.

 

 

정답 코드

import sys
input = sys.stdin.readline

N, K = map(int, input().strip().split())
words = [set([x for x in input().strip()]) for _ in range(N)]
learned_word = [0] * 26

for c in ('a', 'c', 'i', 'n', 't'):
    learned_word[ord(c) - ord('a')] = 1
    
answer = 0
def solve(index, cnt):
    global answer

    if cnt == K-5:
        result = 0
        for word in words:
            check = True
            for w in word:
                if not learned_word[ord(w) - ord('a')]:
                    check = False
                    break
            if check:
                result += 1
        answer = max(answer, result)
        return
    
    for i in range(index, 26):
        if not learned_word[i]:
            learned_word[i] = True
            solve(i, cnt+1)
            learned_word[i] = False


if K < 5:
    print(answer)
elif K == 26:
    print(len(words))
else:
    solve(0, 0)
    print(answer)

 

 

 

오랜만에 풀어봐서 정말 힘들었다. 이제 조금씩 탄력을 붙여나갈 것이다!