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

 

문제 URL:
https://www.acmicpc.net/problem/1411

1411번: 비슷한 단어

 

다음 문제는 단어가 여러 개 주어졌을 때, 숌스러운 단어끼리 몇 개의 쌍이 비슷한지 구하는 프로그램으로

어떤 단어를 숌스럽게 바꾼다는 말은 단어 A에 등장하는 모든 알파벳을 다른 알파벳으로 바꾼다는 소리다.

그리고, 단어에 등장하는 알파벳의 순서는 바뀌지 않는다. 두 개의 다른 알파벳을 하나의 알파벳으로 바꿀 수 없지만,

자기 자신으로 바꾸는 것은 가능하다.

 

이 문제는 각 단어를 모두 숫자로 바꾸어주는 방식을 이용하여 풀었는데 예를 들어 nnmon과 같은 단어는 11231, sstst와 같은 단어는 11212로 치환해주었다.

---

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
using namespace std;

int main() {
	int n;
	vector<string> v, v1;
	int count[27] = { 0, };	//알파벳 개수만큼
	string s, str;
	int ans = 0;

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> s;
		v.push_back(s);	//입력된 모든 단어를 벡터에 저장
	}

	for (int i = 0; i < v.size(); i++) {
		int num = 0;
		memset(count, 0, sizeof(count));	//배열 초기화
		string temp = v[i];
		for (int j = 0; j < temp.size(); j++) {
			if (!count[temp[j] - 'a']) {	//count[해당 알파벳]의 원소가 0일 경우
				num++;
				count[temp[j] - 'a'] = num;	//num(=1,...,n)을 대입
				str += count[temp[j] - 'a'];
			}
			else {	//count[해당 알파벳]의 원소가 0이 아닐 경우(해당 원소에 이미 num이 존재하는 경우)
				str += count[temp[j] - 'a'];
			}
		}
        //새로운 일차원 벡터(=v)로 들어가기 전 v1(정답 보관 벡터)에 str 저장, 각각의 값 초기화
		v1.push_back(str);
		str.clear();
		temp.clear();
	}
	
	//v1에 저장된 각각의 치환값을 비교하여 치환값이 같다면 ans값 증가시킴
	for (int i = 0; i < v1.size(); i++) {
		for (int j = i + 1; j < v1.size(); j++) {
			if (v1[i] == v1[j])
				ans++;
		}
	}

	cout << ans;
}