2607)비슷한 단어

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

같은 구성을 지닌 단어란 알파벳의 종류가 같고, 각 알파벳 별로 갯수가 같은 두 단어를 말한다.

예를들어 기준이 되는 단어 ABC, 다른 단어 CAB는 서로 같은 구성을 가진다.

또 기준이 되는 단어에 알파벳을 하나 넣거나, 빼거나, 바꿀 때 두 단어가 같은 구성이 되면 비슷한 단어가 된다.

예를들어 기준 단어 ABC와 ABCD는 비슷한 단어다. ABC에 D를 넣으면 ABCD와 같은 구성이 되기 때문이다.

ABC와 AB도 비슷한 단어다. ABC에서 C를 빼면 같은 구성이기 때문이다.

ABC와 ABD는 어떨까. C를 D로 바꿔 주면 같은 구성이기 때문에 두 단어는 비슷한 단어다.

위 예를 가지고서 각 알파벳의 갯수를 배열로 표현해보자.

1.ABC와 ABCD는 1110, 1111로 표현할 수 있다. 여기서 각 알파벳 갯수를 빼서 얻은 결과는 000-1이다.

2.ABC와 AB는 1110, 1100으로 표현할 수 있다. 여기서 각 알파벳 갯수를 빼서 얻은 결과는 0010이다.

3.ABC와 ABD는 1110, 1101로 표현할 수 있다. 여기서 각 알파벳 갯수를 빼서 얻은 결과는 001-1이다.

4.ABC와 ABC는 1110,1110으로 표현할 수 있다. 각 알파벳 개수를 빼면 0000이다.

만약 두 단어의 알파벳 갯수를 뺀 결과가 1번처럼 -1만 있을 때 기준 단어에서 알파벳 하나를 채워 같은 구성으로 만들 수 있다.

2번처럼 1만 있을 때는 기준 단어에서 알파벳 하나를 빼어 같은 구성을 만들 수 있고

3번처럼 1,-1만 있을 때는 기준 단어에서 알파벳 하나를 바꿔 같은 구성을 만들 수 있다.

4번 처럼 두 단어가 같은 구성이어서 알파벳 갯수의 차가 0이면 비슷한 단어라고 간주한다.

케바케로 비슷한 단어의 갯수를 세면 된다.

#include<stdio.h>
#include<string.h>
#define ALPHA_NUM 26
#define MAX_LENGTH 10
 
void countAlpha(int cntAlpha[ALPHA_NUM], char word[MAX_LENGTH+1]) {
    for (int i = 0; word[i] != NULL;i++) {
        cntAlpha[word[i]-'A']++;
    }
}
 
void subtractAlphaCnt(int A[ALPHA_NUM], int B[ALPHA_NUM], int result[ALPHA_NUM]) {
    for (int i = 0; i < ALPHA_NUM;i++) {
        result[i] = A[i] - B[i];
    }
}
 
void initAlphaCount(int cntAlpha[ALPHA_NUM]) {
    for (int i = 0; i < ALPHA_NUM;i++) {
        cntAlpha[i] = 0;
    }
}
 
int main() {
    int basedAlphaCnt[ALPHA_NUM] = { 0 };
    int otherAlphaCnt[ALPHA_NUM] = { 0 };
    int resultAlphaCnt[ALPHA_NUM];
    int n;
    int cntSimilar = 0;
    char basedWord[MAX_LENGTH+1];
    char otherWord[MAX_LENGTH + 1];
    int cntMoreAlpha = 0, cntLessAlpha = 0;
 
    scanf("%d",&n);
    scanf("%s",basedWord);
    
    countAlpha(basedAlphaCnt, basedWord);
 
    for (int i = 0; i < n-1;i++) {
        scanf("%s",otherWord);
        countAlpha(otherAlphaCnt, otherWord);
        subtractAlphaCnt(basedAlphaCnt, otherAlphaCnt,resultAlphaCnt);
        initAlphaCount(otherAlphaCnt);
 
        for (int j = 0; j < ALPHA_NUM;j++) {
            if(resultAlphaCnt[j]>0) cntMoreAlpha += resultAlphaCnt[j];
            else if (resultAlphaCnt[j]<0) cntLessAlpha += (-resultAlphaCnt[j]);
        }
 
        if (cntMoreAlpha == 0 && cntLessAlpha == 0) cntSimilar++;
        else if (cntMoreAlpha == 0 && cntLessAlpha == 1) cntSimilar++;
        else if (cntMoreAlpha == 1 && cntLessAlpha == 0) cntSimilar++;
        else if (cntMoreAlpha == 1 && cntLessAlpha == 1) cntSimilar++;
        
        cntMoreAlpha = 0, cntLessAlpha = 0;
    }
    printf("%d\n",cntSimilar);
 
    return 0;
}