서로 순열이 되는 경우를 찾는 트릭(정렬해서 비교하기)

1501번: 영어 읽기

 

영어 단어의 첫글자와 끝글자가 서로 같고 그 사이의 글자가 순서가 뒤섞인채로 구성이 같으면 같은 단어로 취급한다

 

abcde는 acbde, abdce,... 등과 같다

 

단어 사전과 문장들이 주어질때 각 문장을 해석하는 방법의 수를 구한다

 

-------------------------------------------------------------------------------------------------------------------------------------------

 

영어 단어가 bakers, brakes, breaks,...등이 주어질때

 

먼저 bakers를 보면 bakers, bkaers, bekras, berkas, bearks,... 등이 서로 같은 단어들이다.

 

만약에 어떤 문장의 단어 A가 주어질때 bakers와 같은지 다른지를 비교할려면 어떻게 해야할까? 

 

A의 첫글자와 끝글자를 찾은 다음 이것이 b,s인지를 비교한다

 

그리고 그 사이의 글자들이 a,k,e,r로 구성되어있는지를 비교하면 된다

 

이때 정렬해놓으면 순열들은 하나의 고유한 값을 가지게 된다

 

즉, bakers는 [b,s]에 대하여 a,k,e,r을 정렬하여 [a,e,k,r]로 해놓으면 

 

예를 들어 bkaers가 들어올때 먼저 [b,s]로 찾고, k,a,e,r을 정렬하여 [a,e,k,r]이 되므로 서로 같다고 알 수 있게 된다

 

단어의 길이가 100자를 넘지 않기 때문에 10^4 * 10^2*log10^2으로 10^7정도로 시간도 괜찮다

 

from sys import stdin

n = int(stdin.readline())

d = {}

for _ in range(n):
    
    s = stdin.readline().rstrip()
    
    if len(s) == 1:
        
        d[s[0]] = d.get(s[0],0) + 1
    
    else:
        
        if d.get((s[0],s[-1]),0) == 0:

            d[(s[0],s[-1])] = {}

        S = list(s[1:-1])
        S.sort()
        S = ''.join(S)

        d[(s[0],s[-1])][S] = d[(s[0],s[-1])].get(S,0) + 1

 

 

길이가 1인 경우에는 첫글자만 모아두면 될거고

 

이제 이렇게 모아두면 문장을 읽어서 단어 하나씩 끊은 다음 각 단어에 대해서

 

첫글자, 끝글자를 가져와 사전에서 hash한 다음 첫글자와 끝글자 사이를 정렬해서 그것을 키로 가지는 value가

 

몇개인지 알면 각 개수를 곱하면 될 것이다 

 

예를 들어 문장이 A B C로 이루어져있다면 각 단어는 [A,B,C] 3개로 있고

 

A가 몇가지로 해석될 수 있는지 첫글자와 끝글자 A[0], A[-1]을 hash하여 찾고

 

A[1:-1]을 정렬하여 그것이 몇가지 있는지 찾아본다

 

B,C 도 마찬가지

 

그러면 곱의 법칙에 따라 A*B*C가 [A,B,C]가 해석될 수 있는 방법의 수일 것

 

m = int(stdin.readline())

for _ in range(m):
    
    s = list(stdin.readline().rstrip().split())

    count = 1

    for c in s:
        
        if len(c) == 1:
            
            count *= d.get(c[0],0)
        
        else:
            
            C = list(c[1:-1])
            C.sort()
            C = ''.join(C)

            count *= d.get((c[0],c[-1]),{}).get(C,0)
    
    print(count)