[백준][C++] 1411: 비슷한 단어

문제 링크: https://www.acmicpc.net/problem/1411

 

두 단어가 비슷한 단어인지 확인하려면 둘다 동일한 형태로 변환시켰을 때 동일하면 비슷하다고 할 수 있습니다.

변환 방법은 맨 앞에서부터 등장하는 알파벳을 a, b, c, ... 순으로 매핑해서 변환하는 겁니다. 예를들어 xxzbc는 x가 첫번째, z가 두번째, b가 세번째, c가 네번째니 변환해보면 aabcd 이렇게 되겠습니다.

전 이런식으로 했는데 뭐 다른 방법도 많습니다

#include <bits/stdc++.h>
using namespace std;

bool similar(string a, string b) {
	// base
	if (a.size() != b.size()) return false;

	int counter = 0;
	map<char, char> conv;

	for (auto& c : a) {
		if (!conv.count(c))
			conv[c] = 'a' + (counter++);
		c = conv[c];
	}

	counter = 0;
	conv.clear();
	for (auto& c : b) {
		if (!conv.count(c))
			conv[c] = 'a' + (counter++);
		c = conv[c];
	}

	return a == b;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

	int n;
	cin >> n;
	vector<string> v(n);
	for (auto& s : v)
		cin >> s;

	int cnt=0;
	for (int i = 0; i < n - 1; ++i)
		for (int j = i + 1; j < n; ++j)
			if (similar(v[i], v[j]))
				++cnt;
	cout << cnt << '\n';
	
	return 0;
}