[백준 1099번] 파이썬 - 알 수 없는 문장

백준 1099 - 알 수 없는 문장

시간 제한 2초, 메모리 제한 128MB

# 조건

• 형택이와 그의 친구들은 자꾸 다른 사람들이 대화를 엿듣는 것이 짜증났다.
• 따라서, 새로운 언어를 만들었다.
• 이 언어에는 단어가 N개 있다.
• 그리고 이 언어의 문장은 단어를 공백없이 붙여쓴 것이다.
• 이 문장에서 각 단어는 0번 또는 그 이상 나타날 수 있다.
• 이 언어가 형택스러운 이유는 (특별한 이유는) 단어에 쓰여 있는 문자의 순서를 바꿔도 되기 때문이다.
• 이때, 원래 단어의 위치와 다른 위치에 있는 문자의 개수 만큼이 그 순서를 바꾼 단어를 만드는 비용이다.
  • 예를 들어, abc란 단어가 있을 때, abc는 비용 0으로 만들 수 있고, acb, cba, bac는 비용 2로 바꿀 수 있고, bca, cab는 비용 3으로 바꿀 수 있다.
• 따라서, 한 문장을 여러 가지 방법으로 해석할 수 있다.
• 이때 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력

• 첫째 줄에 문장이 주어진다.
• 문장의 길이는 최대 50이다.
• 둘째 줄에 단어의 개수 N이 주어지며, N은 50보다 작거나 같은 자연수이다.
• 셋째 줄부터 N개의 줄에 각 단어가 주어진다. 단어의 길이는 최대 50이다.
• 문장과 단어는 알파벳 소문자로만 이루어져 있다

출력

• 첫 째 줄에 문제의 정답을 출력한다.
• 만약 문장을 해석할 수 없다면 -1을 출력한다.

# 접근 방법

• 주어지는 단어가 문장안에 온전히 들어있는지 파악하기 위해서는 브루트포스를 사용해주면 된다.
• 다만, 이 때 어떤 단어를 선택하냐에 따라서 최소값이 달라질 수 있기 때문에 dp를 사용해준다.
  • dp의 값은 충분히 큰 수로 설정해준 후, min 비교를 위해 0번 인덱스에 0을 추가해준다.
  • 이후, 모든 철자가 현재 비교 단어와 일치한다면 문장에 시작하는 인덱스 + 해석하는데 필요한 값 vs 현재 기록되어있는 값을 비교하여 최소를 갱신해준다.
• 브루트 포스로 비교하기 위해서는 문장 중간에 해당 값이 들어있을 수 있으므로 1단어씩 줄여주며 비교해준다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from collections import defaultdict  

# 문장 받아주기  
sent = list(input().rstrip())  
N = int(input())  
words = []  
alpha = dict()  

# 비교할 단어들 저장해주기  
# 단어들마다 들어가는 알파벳으로 기록해준다.  
# 딕셔너리로 저장해야 o n e 와 e n o 가 같은 철자라는 것을 확인 가능함  
for i in range(N):  
    word = input().rstrip()  
    words.append(word)  
    alpha[word] = defaultdict(int)  
    for w in word:  
        alpha[word][w] += 1  

# dp 사용해주는데  
# dp의 인덱스는 해석된 단어의 인덱스  
# neotow에서 two를 비교했다면 -> dp[5]에 기록된다.  
# dp 갱신은 앞선 단어를 해석하는데 필요한 값 + 현재 비교한 단어의 값 vs 기록되어 있는  
# 최초 값이 존재하지 않으므로 임의의 0번 인덱스에 0 추가  
dp = [0] + [1000] * len(sent)  

# 문장의 중간에 비교해야되는 값이 있으므로  
# 1글자씩 늘려주면서 비교해준다 -> neotow이면 n, ne, neo, neot, neoto ---  
for start in range(len(sent)):  
    for end in range(start, len(sent)):  
        temp = defaultdict(int)  
        comp = sent[start:end+1]  
        for c in comp:  
            temp[c] += 1  

        # 현재 문장에서 자른 단어와 철자가 같은 단어가 있는지 체크  
        # 딕셔너리끼리 비교해준다.        
        for word in words:  
            if alpha[word] != temp:  
                continue  

            # 철자 같다면 해석비용  
            cnt = 0  
            for j in range(len(word)):  
                if word[j] != comp[j]:  
                    cnt += 1  

            # 임의의 0번 인덱스를 추가하였으므로 end+1에 기록해준다.  
            dp[end+1] = min(dp[end+1], dp[start] + cnt)  

print(dp[-1] if dp[-1] != 1000 else -1)