[Python3] 백준 - 1501 영어 읽기

www.acmicpc.net/problem/1501

1501번: 영어 읽기

- 접근법

 

주의) 이 문제에서 N개의 단어가 주어지고 M개의 해석할 '문장'이 주어진다.

 

abcde와 같은 단어는, abcde, abdce, acbde, acdbe, adbce, adcbe 같은 단어들로 해석될 수도 있다.

 

결국 문자의 첫 글자, 마지막 글자가 같고 이것을 제외한 문자들의 존재 빈도가 같으면 같은 단어로 해석될 수 있다.

이 문제는 단어가 10000개, 그리고 길이가 100자까지 들어올 수 있으므로 앞뒤글자를 빼고 브루트포스로 모든 경우를 다 찾아 확인하면 시간초과가 난다.

따라서 효율적으로 확인하기 위해서는 앞 뒤 문자를 제외하고 나머지 문자들의 빈도수만 확인하면 된다.

 

가장 먼저 생각해볼 수 있는 것은 앞 뒤 문자를 제외하고 나머지 문자들의 빈도수들을 dict에 따로 카운팅해서 알파벳별로 저장하여 비교하는 방법을 생각할 수 있지만, 이러한 방법은 확인 시에 불필요한 탐색이 많이 요구된다. (X)

 

그렇기 때문에, 가장 좋은 방법은 앞 뒤 글자를 제외하고 나머지 글자를 정렬하면 손쉽게 비교할 수 있을 것이다.

 

bcd 

bdc -> bcd

cbd -> bcd

cdb -> bcd

 

이와 같이 결국 각 알파벳 빈도수가 같은 경우를 정렬하면 모두 하나의 Key로 통일시킬 수 있다.

 

따라서 나는 예를 들어 abdce 의 단어가 들어온다면 앞 뒤 글자 ae를 First_Key 로 쓰고 bdc를 정렬하여 bcd 로 Second_Key로 만들어 2차원 Dict 자료구조를 생성하여 dict[First_Key][Second_Key]로 한번 Dict를 완성시켜놓으면 O(1)로 확인할 수 있게 구성하였다.

 

물론 1글자, 2글자가 들어올 경우를 대비하여 예외처리는 꼭 해줘야한다.

 

---

- 소스코드

# 사전 등록
# 앞뒤 문자가 첫번째 key / 나머지 문자들은 sort하여 두번째 key로 생성
N=int(sys.stdin.readline().rstrip())
for _ in range(0,N) :
    word=sys.stdin.readline().rstrip()
    if len(word)>1:
        first_key=word[0]+word[-1]
    else :
        first_key=word[0]
    if len(word)>2:
        second_key=''.join(sorted(word[1:-1]))
    else :
        second_key=''
    word_dict[first_key][second_key]+=1
 
# 해석
# 사전 등록 과정과 마찬가지로 첫번째 key와 두번째 key 를 만들어서 접근
M=int(sys.stdin.readline().rstrip())
for _ in range(0,M) :
    decode_sentence=sys.stdin.readline().rstrip().split()
    answer_list=[]
    answer=1
    for word in decode_sentence :
        if len(word)>1 :
            first_key = word[0] + word[-1]
        else :
            first_key=word[0]
        if len(word)>2 :
            second_key = ''.join(sorted(word[1:-1]))
        else :
            second_key=''
        answer_list.append(word_dict[first_key][second_key])
    for num in answer_list :
        answer*=num
    print(answer)
 
if N==0 and M==0 :
    print("0")