[Olympiad] 지역본선 2004 초등부 : 비슷한 단어 #2607

문제 링크

비슷한 단어

문제 요약

• 첫째 줄에는 단어의 개수가 주어지고 둘째 줄부터는 한 줄에 하나씩 단어가 주어진다.
• 모든 단어는 영문 알파벳 대문자로 이루어져 있다.
• 단어의 개수는 100개 이하이며, 각 단어의 길이는 10 이하이다.
• 한 단어에서 한 문자를 더하거나, 빼거나, 하나의 문자를 다른 문자로 바꾸어 한 단어와 같은 구성을 갖게 되는 경우에 두 단어를 서로 비슷한 단어라고 한다.
• 첫째 줄에 입력으로 주어진 첫 번째 단어와 비슷한 단어가 몇 개인지 출력한다.

조건문

• change : 문자가 추가됐을 때에는 ++, 문자가 감소됐을 때에는 --
• changeCnt : 문자가 변경되었을 때 ++
• 첫 번째 단어를 A라 칭하고 그 외의 단어들은 B라고 칭하자.
  • A에서 문자의 개수를 check 배열에 저장하고
  • B에서 문자의 개수를 check2 배열에 저장한다.
  • check와 check2의 문자의 개수를 비교해준다.
• 비교 순서
  1. check[i]와 check2[i]가 같을 때
     • 다음 문자를 비교해준다.
  2. check[i]와 check2[i]의 차이가 1일 때
     • change++, changeCnt++
  3. check[i]와 check2[i]의 차이가 -1일 때
     • change--, changeCnt++
  4. 그 외
     • break

문제 해답

#include <iostream>
#include <string>
using namespace std;
const int ALPHA = 26;
int check[ALPHA];
int check2[ALPHA];
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N, strSz;
    int res = 0;
    string str, firstStr;
    cin >> N;
    cin >> firstStr;
    for (int i = 0;i < firstStr.size();i++)
        check[firstStr[i] - 'A']++;
    for (int i = 1;i < N;i++) {
        int change = 0;
        int changeCnt = 0;
        bool fail = false;
        cin >> str;
        strSz = str.size();
        for (int i = 0;i < strSz;i++) {
            check2[str[i] - 'A']++;
        }
        for (int i = 0;i < ALPHA;i++) {
            if (check[i] == check2[i])
                continue;
            else if (check[i] == check2[i] - 1) {
                change++;
                changeCnt++;
            }
            else if (check[i] == check2[i] + 1) {
                change--;
                changeCnt++;
            }
            else if (check[i] > check2[i]) {
                fail = true;
                break;
            }
            else if (check[i] < check2[i]) {
                fail = true;
                break;
            }
        }
        for (int i = 0;i < ALPHA;i++)
            check2[i] = 0;
        if (fail || changeCnt > 2 || change > 1 || change < -1) {
            continue;
        }
        res++;
    }
    cout << res << endl;
}