[백준/Python] 1501. 영어 읽기

문제

https://www.acmicpc.net/problem/1501

1501번: 영어 읽기

풀이

문장을 해석할 수 있는 경우의 수를 구해야 한다. 

문장을 공백을 기준으로 잘라서 단어들로 만들었다.

각 단어들은 맨 앞과 맨 뒷 글자를 제외하고 순서를 바꾸어 다양한 경우의 수를 만들 수 있다. 

이 경우의 수 중에 사전에서 찾을 수 있는 경우의 수가 필요하다. 

 

중간에 헷갈렸던 점은, 

어떤  문장이 3개의 단어로 구성되어 있고, 각각 2가지, 0가지, 3가지로 해석될 수 있는 경우에 

2*0*3 = 0이 아니라, 0은 없는 셈 치고 2*3 = 6이 답이 된다는 것이었다. 

 

자료구조로 dict를 이용하였는데, key를 "(맨앞글자)(맨뒷글자)(가운데문자들정렬)"로 이용하였다. 

예를들어 "befakdf" 는 "bfadefk"가 된다. 

따라서, 사전에 "abec"와 "aebc"가 있다면 이 둘의 key는 같다. 

그래서 value는 해당 key가 등장한 횟수를 넣어주었다. 

 

사전을 모두 만든 후에 

 

문장에 있는 단어들을 dict에서 key를 만든 방법과 동일하게 만들어서, 사전에서 value를 조회한 뒤 value가 0이 아닐 경우에만 곱해주었다. 

 

* 위에서 key를 만드는 방법에서, 1글자와 2글자짜리는 if로 검사해서 따로 key를 만들어주었다. 

코드

from collections import defaultdict
dic = defaultdict(dict)

N = int(input())
for i in range(N):
    word = input()
    if (len(word) <= 2):
        try : dic[word]['']+=1
        except : dic[word]['']=1
    else:
        first_k = word[0]+word[-1]
        sec_k = str(sorted(word[1:-1]))
        try : dic[first_k][sec_k]+=1
        except : dic[first_k][sec_k]=1
        
M = int(input())
for i in range(M):
    sen = input().split(' ')
    count = 1
    isCan = False
    for idx, w in enumerate(sen):
        temp = 0
        if (len(w) <= 2):
            try :temp += dic[w]['']
            except: temp
        else:
            start = w[0]
            end = w[-1]
            middle = str(sorted(w[1:-1]))
            try: temp+= dic[start+end][middle]
            except: temp
        if temp != 0:
            count*=temp
            isCan = True
    if not isCan:
        count = 0
    print(count)

python으로 어려운 문제를 푸는 것이 처음이라 알고리즘을 구현하는 부분을 굉장히 헤맸다. 

결과