#1411 비슷한 단어(String Process)

문자 대치법으로 단어를 변경할 수 있으면 비슷한 단어라고 할 때, 주어진 문자열 중에 몇쌍이 비슷한 단어가 되는지가 문제입니다.

 

예를 들어서 aab 와 bbc 는 비슷한 단어가 됩니다.  a를 b로 바꾸고, b를 c로 바꾸면 되니까요.  그 역으로도 성립해야 하는데, b를 a로 바꾸고, c를 b로 바꾸면 됩니다.

 

이를 위해서 두개의 배열을 선언했습니다.  첫번째 배열은 첫번째 문자열에서 두번째 문자열로 변경될 변환테이블이고, 두번째 배열은 중복된 문자가 변환테이블에 있는지 검사하는 용도입니다.  중복된 문자가 변환테이블에 발생하면, 역이 성립하지 않으니까요.  수학 함수로 따지면 일대일 대응이 되어야 역함수가 존재하는 것과 같은 이치입니다.

 

문제 난이도는 Silver II로 꽤 쉽습니다.

 

제가 구현한 소스입니다. 

이 소스에서 핵심은 두개의 문자열이 비슷한 문자열인지 검사하는 cmp 함수입니다.  두번째 문자열에서 변환테이블에 없는 문자가 발생한 경우에, 첫번째 문자열의 해당 위치의 문자가 이미 변환테이블에 존재한다면, 실패한 것이므로 false를 반환하고, 그렇지 않다면, 변환테이블에 첫번째 문자열의 해당 위치 문자를 등록합니다.

이미 변환테이블에 해당 문자가 있다면, 그 문자값과 첫번째 문자열의 해당 문자와 다르면 역시 false를 반환합니다.  최종적으로 모든 문자들에 대해서 이 과정이 제대로 끝나면, true를 반환합니다.

 

//----------------------------------------------------------
//  baekjoon #1411 - Similar Words
//    - by Aubrey Choi
//    - created at 2020-03-03
//----------------------------------------------------------
#include <stdio.h>

bool cmp(const char *a, const char *b)
{
  char z[26]={0,}, q[26]={0,};
  int i;
  for(i=0;a[i];i++)
  {
    int s = a[i]-'a', t = b[i]-'a';
    if(!z[t])
    {
      if(q[s]) return false;
      z[t]=a[i];
      q[s]=1;
      continue; 
    }
    if(z[t]!=a[i]) return false;
  }
  return true;
}
int main()
{
  int n, cnt=0, i, j;
  char word[100][52];
  scanf("%d",&n);
  for(i=0;i<n;i++)
  {
    scanf("%s", word[i]);
    for(j=0;j<i;j++) if(cmp(word[i],word[j])) cnt++;
  }
  printf("%d\n", cnt);
}