BOJ 1411 비슷한 단어

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

문제

만약 어떤 단어A를 숌스럽게 바꿔서 또다른 단어 B로 만든다면, 그 단어는 비슷한 단어라고 한다.

어떤 단어를 숌스럽게 바꾼다는 말은 단어 A에 등장하는 모든 알파벳을 다른 알파벳으로 바꾼다는 소리다. 그리고, 단어에 등장하는 알파벳의 순서는 바뀌지 않는다. 두 개의 다른 알파벳을 하나의 알파벳으로 바꿀 수 없고, 임의의 알파벳을 자기 자신으로 바꾸는 것은 가능하다.

예를 들어, 단어 abca와 zbxz는 비슷하다. 그 이유는 a를 z로 바꾸고, b는 그대로 b, c를 x로 바꾸면, abca가 zbxz가된다.

단어가 여러 개 주어졌을 때, 몇 개의 쌍이 비슷한지 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에 단어의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에 한 줄에 하나씩 단어가 주어진다. 단어의 길이는 최대 50이고, N은 100보다 작거나 같은 자연수이다. 모든 단어의 길이는 같고, 중복되지 않는다. 또, 알파벳 소문자로만 이루어져 있다.

---

출력

첫째 줄에 총 몇 개의 쌍이 비슷한지 출력한다.

---

예제 입력 1

5
aa
ab
bb
cc
cd

예제 출력 1

4

예제 입력 2

3
abca
zbxz
opqr

예제 출력 2

1

… 이하 예제 생략

---

코드

이번 문제는 비슷한 단어 쌍의 수를 구하는 문제이다.

비슷한 단어를 찾는 방법은 간단하다.

각 단어를 알파벳 대신에 각 알파벳의 첫 등장 순서로 해당 알파벳들을 대체시켜 주면 된다.

abca를 예시로 변환시켜보면, 다음과 같다.

1. 1

   a가 처음 등장하기 때문에 a를 뜻하는 1 추가

2. 12

   b가 두 번째로 등장하기 때문에 b를 뜻하는 2 추가

3. 123

   c가 세 번째로 등장하기 때문에 c를 뜻하는 3 추가

4. 1231

   마지막으로 첫 번째에 등장하는 a이기 때문에 1 추가

위와 같은 방식으로 변환하면, abca나 xyzx나 전부 1231로 변환되어 똑같은 형태가 된다.

똑같은 형태는 비슷한 단어라고 볼 수 있기 때문에, 동일한 형태를 이루는 쌍을 세어주기만 하면 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    static int N;
    static String[] formOfWord;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        formOfWord = new String[N];
        for (int i = 0; i < N; i++) {
            int checkIndex = 1;
            int[] indexOfAlphabets = new int[26];
            StringBuilder indexForm = new StringBuilder();
            char[] input = br.readLine().toCharArray();
            for (char alphabet: input) {
                int orderOfAlphabet = alphabet - 'a';

                if(indexOfAlphabets[orderOfAlphabet] != 0) {
                    indexForm.append(indexOfAlphabets[orderOfAlphabet]);
                } else {
                    indexOfAlphabets[orderOfAlphabet] = checkIndex;
                    indexForm.append(checkIndex);
                    checkIndex++;
                }
            }

            formOfWord[i] = indexForm.toString();
        }

        int answer = countPairs();
        System.out.println(answer);
    }

    static int countPairs() {
        int count = 0;

        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                if(formOfWord[i].equals(formOfWord[j])) {
                    count++;
                }
            }
        }

        return count;
    }
}