[BOJ] 2607번: 비슷한 단어

2607번: 비슷한 단어

문제 요약

조건에 따라 첫 번째 단어와 비슷한 단어의 개수를 출력한다.

조건

• 같은 구성이란:

  1. 두 단어가 같은 종류의 문자로 이루어져 있다.
  2. 같은 문자는 같은 개수만큼 있다.

• 같은 종류의 문자가 같은 개수만큼 있거나, 한 단어에서 문자를 더하거나 빼거나 한 문자를 다른 문자로 바꾸거나 해서 같은 구성을 만들면 비슷한 단어로 취급한다.

단어의 변형을 한 번만 할 수 있기 때문에 단어의 길이 차이가 1 이하여야 한다.

그리고 문자 차이가 2개 이하여야 한다.

BOJ, BOI 두 단어가 있을 때, 문자의 차이는 2개다. 그렇지만 I를 J로 바꿔주면 비슷한 단어가 된다.

코드

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

int n, ans = 0;

bool check(const array<int, 26> &va, const array<int, 26> &first)
{
    int c = 0, vac = 0, firstc = 0;
    for (int i = 0; i < 26; ++i)
    {
        vac += va[i];
        firstc += first[i];
        c += abs(va[i] - first[i]);
    }
    if (c <= 2 && abs(vac - firstc) <= 1)
        return true;
    else
        return false;
}

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cin >> n;
    string first;
    cin >> first;
    array<int, 26> firAlpha = {
        0,
    };
    for (int i = 0; i < first.size(); ++i)
        firAlpha[first[i] - 'A']++;
    for (int i = 1; i < n; ++i)
    {
        string s;
        cin >> s;
        array<int, 26> alpha = {
            0,
        };
        for (int i = 0; i < s.size(); ++i)
            ++alpha[s[i] - 'A'];
        if (check(alpha, firAlpha))
            ++ans;
    }
    cout << ans;
    return 0;
}