백준 1411 비슷한 단어 / python

문제 : 1411

풀이 point

패턴이 같으면 단어를 변경했을 때 비슷한 단어임을 알 수 있다.

예를들면, abca zbxz의 경우
몇번째의 등장을 하는지를 체크하면 패턴을 만들 수 있다.

abca -> a는 첫번째로 등장, b는 두번째로 등장, c는 세번째로 등장(1231)
zbxz -> z는 첫번째로 등장, b는 두번째로 등장, x는 세번째로 등장(1231) 
opqr -> o는 첫번째로 등장, p는 두번째로 등장, q는 네번째로 등장, r은 다섯번째로 등장(1234)

즉 패턴이 같은 abca&zbxz는 비슷한 단어이고 패턴이 다른 opqr은 비슷한 단어가 아니다.

풀이 코드

N = int(input())

count = {}
for _ in range(N):
  seq = 0
  pattern = []
  mapping = {}

  words = input()
  for w in words:
    if w not in mapping:
      mapping[w] = seq
      seq += 1
    pattern.append(mapping[w])
  
  p = tuple(pattern)
  if p in count:
    count[p] += 1
  else:
    count[p] = 1

ans = 0
for cnt in count.values():
  ans += cnt*(cnt-1)//2

print(ans)