[Python] 백준 #1411 - 비슷한 단어

문제

---

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

1411번: 비슷한 단어

 

 

 

풀이

---

from itertools import combinations

n = int(input())
ss = []
for _ in range(n):
    tmp = input()
    ss.append(tmp)

cnt=0

for s in list(combinations(ss,2)):
    dic = {chr(ord('a')+i):0 for i in range(26)}
    for i in range(len(s[0])):
        if dic[s[0][i]] == 0: # 바꾸지 않았으면
            if s[1][i] not in dic.values(): # 변경된 문자열이 존재하지 않으면
                dic[s[0][i]] = s[1][i] # 변경
            else: # 이미 바꾼 문자열이면
                break # 멈춤
        else: # 변경했으면
            if dic[s[0][i]] != s[1][i]: # 문자열이 다르면
                break # 멈춤
    else:
        cnt+=1
print(cnt)

 

딕셔너리를 사용하여 변경한 문자를 체크하면서 구해주었다.

 

딕셔너리 초기값을 0으로 하고 문자열을 변경 할 때 변경한 문자열으로 바꿔준다.

 

만약 한번도 바뀌지 않은 문자열이면 변경할 문자열이 예전에 바꾼 문자열이 아닌것을 체크해준다.

이 조건을 만족하기 위해 예전에 바꾼 문자열이 아닌것을 체크 -> (두 개의 다른 알파벳을 하나의 알파벳으로 바꿀 수 없지만, 자기 자신으로 바꾸는 것은 가능하다.)

 

예전에 바꾼 문자열이 아닐 경우, 딕셔너리를 변경해주고,

이미 바꾼 문자열이면 break 해준다.

 

이미 딕셔너리를 바꿨으면, 딕셔너리 값과 바꿀 문자열을 비교해준다.