BOJ 1411 - 비슷한 단어

문제

N개의 단어가 주어질 때, 문자 대응 패턴(구조)이 동일한 쌍의 개수를 구하라. 예를 들어 "aba"와 "xyx"는 같은 패턴이다.

입력

첫째 줄에 N, 이후 N줄에 각 단어가 주어진다 (같은 길이).

출력

비슷한 단어 쌍의 수를 출력한다.

예제

입력	출력
`3` `aa` `ab` `cc`	`1`

풀이

각 단어의 문자를 등장 순서대로 숫자로 치환하여 정규화된 패턴을 만든 뒤, 모든 쌍을 비교한다.

각 단어에서 처음 등장하는 문자는 1, 다음 새 문자는 2, ... 식으로 번호를 매긴다 (예: "aba" → "121")
이렇게 정규화된 패턴 문자열을 리스트에 저장한다
모든 쌍 (i, j)에 대해 패턴이 같으면 카운트한다

핵심 아이디어: 문자 자체가 아니라 등장 순서 패턴으로 변환하면, 구조가 같은 단어는 동일한 패턴 문자열을 갖게 되어 O(1) 비교가 가능하다.

코드

import sys
 
input = sys.stdin.readline
 
n = int(input())
lst = []
for _ in range(n):
    a = list(input().strip())
    d = {}
    tmp = 1
    for j in range(len(a)):
        if a[j] not in d:
            d[a[j]] = tmp
            a[j] = d[a[j]]
            tmp += 1
        else:
            a[j] = d[a[j]]
    lst.append("".join(map(str, a)))
 
ans = 0
 
for i in range(n - 1):
    for j in range(i + 1, n):
        if lst[i] == lst[j]:
            ans += 1
 
print(ans)

복잡도

시간: O(N^2 * L) (L은 단어 길이)
공간: O(N * L)

문제