백준 1411번 비슷한 단어

 

문제

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

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

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

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

입력

첫째 줄에 단어의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에 한 줄에 하나씩 단어가 주어진다. 단어의 길이는 최대 50이고, N은 100보다 작거나 같은 자연수이다. 각각의 단어는 모두 다르다.

출력

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

 

 

 

이게 그냥 visit에 자신을 넣고 visit에 있던 값이 들어왔을 때 그 값이 현재의 자신의 인덱스의 값과 같으면 일치하는 걸로 하면은 반례가 생김 abb dcd같은 경우 둘다 b에 b가 들어오고 d에 d가 들어오므로 비슷한 단어로 여기게 되는데

이렇게 하는 것이 아니고 a bb 같은 식으로 b가 붙어서 나오는 것과 d가 따로 나오는건 다른 케이스이므로 a위치에 d가 들어가고 b위치에 c가 들어가고 다시 b위치에 d가들어가게 되면서 순서가 다른게 증명됨 c가 들어와야 일치 

 

 

 

#include <iostream>
#include <string>

using namespace std;
string str[100];

bool check(int i , int j)
{
if(str[i].size() != str[j].size())
return false;

char visit1[26] = {0};
char visit2[26] = {0};

for(int k = 0; k<str[i].size(); k++)
{
if(!visit1[str[i][k] - 'a'] && !visit2[str[j][k] - 'a'])
{
visit1[str[i][k] - 'a'] = str[j][k];
visit2[str[j][k] - 'a'] = str[i][k];

}
else if(visit1[str[i][k] - 'a'] != str[j][k] || visit2[str[j][k]- 'a'] != str[i][k])
{
return false;
}
}

return true;



}






int main(void)
{
int result = 0;
int N;
cin >> N;

for(int i =0 ; i<N; i++)
{
cin >> str[i];
}

for(int i =0; i<N; i++)
{
for(int j=i+1; j<N; j++)
{
if(check(i,j))
         result++;
}
}

cout << result;



}