[백준-파이썬] 1501: 영어 읽기

문제 보러 가기!

처음에 아이디어가 딱 떠올랐다 !
그 후에 문제를 잘 이해하지 못해서, 조건 생각 못해서 틀리다가 맞았다 !!
정답률이 낮은 이유를 알 것 같다.. 꼼꼼하게 문제를 읽어야 겠다..!! 

사전에 있는 단어가 들어온다.
그 후에 문장이 들어온다. 그 문장을 해석하는 경우의 수를 출력하는 문제이다!
그 문장의 단어들이 사전에 있는 단어와 첫 글자와 끝 글자가 일치하고, 가운데 글자들이 있으면 해석될 수 있다. 예를 들어서 사전에 abc, cba가 있는데, 'acb'가 들어오면 두 가지 방식으로 해석될 수 있는 것이다.

그래서 2차원 리스트, defaultdict을 이용해서, 어떤 단어가 들어왔을 때 몇 가지 방식으로 해석될 수 있는지 개수를 저장했다. 2차원 리스트를 53X 53로 만들었다. 알파벳이 26글자이고 대소문자를 구분하기 때문이다! 또 단어 글자가 한 개인 경우를 따로 처리하기 위해서 리스트 크기를 하나 더 만들었다. 2차원 리스트 안에는 defaultdict(int)를 마련해뒀다.

단어가 들어오면 첫 글자, 끝 글자를 아스키 숫자로 보았다. 대문자이면 65를 빼고, 소문자이면 71을 빼서 2차원 리스트에 저장했다.

그 사이 글자들은 어떤 순서대로 배치되든 다 같은 경우로 보므로, sort한 상태로 defaultdict에서 개수를 더했다. 이때 key는 그 중간 글자들을 sort해서 str 형태로 만든 것이고, value는 1씩 더했다. defaultdict이라서 디폴트값은 0이라서 편하다 😻😻

그 후에 문장들이 들어오면, 단어 별로 그 단어가 몇 가지 방식으로 해석될 수 있는지 곱했다. 곱해야 하니까 처음에 ans를 1로 두고, 각 경우를 곱해갔다. (단어가 해석될 수 없는 경우는 0이 곱해지니까 답은 자연스럽게 0이 된다.)

-> 처음에는 문장이 아니라 단어가 들어오는 줄 알아서 틀렸다..ㅠㅠ 질문 게시판 엔젤님의 글을 보고, 문제를 잘못 이해한 걸 알고 그걸 고려해서 풀었다.

그래도 틀려서 좀 더 고민해보니까, 시작 글자==끝 글자인 경우.. 즉 단어가 1글자로 이뤄진 경우가 있었다! 이런 경우는 따로 처리하니 맞았다 ! 

import sys
from collections import defaultdict

input = sys.stdin.readline
MIISS = lambda: map(int, input().strip().split())

N = int(input())
dictionary = [[defaultdict(int) for _ in range(53)] for _ in range(53)]  # 세로: 시작, 가로: 끝나는 글자. 대->소


def find_num(letter):
    letter_num = ord(letter)
    if 65 <= letter_num <= 90:  # 대문자이면
        return letter_num - 65
    else:
        return letter_num - 71


for _ in range(N):
    tmp = input().strip()  # 단어가 들어온다.

    # 그 단어가 한 글자인 경우..!
    if len(tmp) == 1:
        # 시작 글자
        start_num_final = find_num(tmp[0])

        dictionary[start_num_final][52][''.join(sorted(tmp[1:-1]))] += 1
        # 끝나는 글자 52 위치에 따로 처리..

    else:
        start, end = tmp[0], tmp[-1]

        # 시작 글자, 끝 글자 숫자 구하기
        start_num_final, end_num_final = find_num(start), find_num(end)

        dictionary[start_num_final][end_num_final][''.join(sorted(tmp[1:-1]))] += 1
        # 첫글자, 끝글자에 해당하는 리스트 위치에 딕셔너리 있음. key: 중간 글자들을 정렬해서 | value: 갯수 1 더함(디폴트 0)

M = int(input())
for _ in range(M):
    sentence = list(input().strip().split())  # 문장이 들어온다(한 단어 이상)

    ans = 1

    # 한 문장이 여러 단어로 이뤄져 있을 수 있음!!
    for i in range(len(sentence)):
        tmp = sentence[i]

        # 그 단어가 한 글자인 경우..!
        if len(tmp) == 1:
            start_num_final = find_num(tmp[0])

            ans *= dictionary[start_num_final][52][''.join(sorted(tmp[1:-1]))]

        else:
            start, end = tmp[0], tmp[-1]

            # 시작 글자, 끝 글자 숫자 구하기
            start_num_final, end_num_final = find_num(start), find_num(end)

            ans *= dictionary[start_num_final][end_num_final][''.join(sorted(tmp[1:-1]))]

    print(ans)