[백준 1411][파이썬] 비슷한 단어

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

1411번: 비슷한 단어

 

시간 복잡도를 줄이기 위해서 전처리 과정을 진행했다.

 

각 문자를 해당 문자가 처음 등장한 순서로 변경한다.

 

'cacccdaabc'를 기준으로 보면 c는 처음 등장했기 때문에 1이고 a는 두 번째 등장했기 때문에 2이고 c는 세 번째 등장했기 때문에 3이다.

 

이런 식으로 문자열을 변환하면 '1211132241'이 된다.

 

그 다음 'cdcccaddbc'도 동일하게 변환하면 '1211132241'이 된다.

 

이제 이렇게 변환한 문자열을 비교해서 동일하면 두 문자열은 '비슷한 단어'가 된다.

 

물론 알파벳은 26개 있기 때문에 숫자를 기준으로 하면 두 자리가 넘어가서 문제가 발생할 수 있다.

 

그래서 변환한 숫자를 아스키 코드로 취급하여 다시 알파벳으로 바꾼다.

 

<최종 코드>

import sys
sys.setrecursionlimit(int(1e9))
input=sys.stdin.readline
n=int(input())
arr=[input().rstrip() for _ in range(n)]
def transform(s): # 문자열을 숫자로 변환
    temp=[-1]*26 # 알파벳 등장 여부
    res='' 
    cnt=0
    for i in s:
        idx=ord(i)-ord('a')
        if temp[idx]==-1: # 첫 등장이라면?
            cnt+=1
            temp[idx]=cnt
        res+=chr(temp[idx]+ord('a')-1)
    return res
transform_arr=[transform(i) for i in arr]
cnt=0
for i in range(n):
    for j in range(i+1, n):
        if transform_arr[i]==transform_arr[j]:
            cnt+=1
print(cnt)