백준 2607번: 비슷한 단어

백준 온라인 저지(BOJ) 2607번 문제

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

1. 문제 요약

두 단어가 같은 문자로 이루어져 있고, 각 문자별로 갯수가 같으면 두 단어를 '같은 구성을 갖는다'고 한다.

한 단어에서 한 문자를 추가or삭제or다른 문자로 바꾸었을 때 구성이 같아지면 두 단어는 '비슷하다'고 한다. (같은 구성을 갖는 것은 비슷한 것에 포함된다.)

첫 번째 단어와 비슷한 단어가 총 몇 개인지 출력하라.

2. 알고리즘

뭔가 복잡하게 짠 기분이 들지만,

각 알파벳별로 갯수를 세고

차이가 2 이상인 것이 있을 경우 X

갯수가 차이나는 것이 3개 이상인 경우 X

갯수가 차이나는 것이 2개인 경우 서로 바뀐 것이면 O, 아니면 X

를 통해 판별하였다.

3. 코드

#include <iostream>
using namespace std;

bool sim(int* a, int* b) {
	int s = 0, first = -1;
	for (int i = 0; i < 26; ++i) {
		if (a[i] != b[i]) {
			if (first == -1) first = i;
			if (a[i] - b[i] > 1 || a[i] - b[i] < -1) return false;
			else {
				++s;
				if (s == 2) if ((a[first] + a[i]) != (b[first] + b[i])) return false;
				if (s >= 3) return false;
			}
		}
	}
	return true;
}

int main() {
	int n, i, count = 0;
	char ori[15];
	char buf[15];
	int c1[26] = { 0 };

	scanf("%d", &n);
	scanf("%s", ori);
	i = 0;
	while (ori[i]) ++c1[ori[i++] - 'A'];
	for (int j = 1; j < n; ++j) {
		scanf("%s", buf);
		int c2[26] = { 0 };
		i = 0;
		while (buf[i]) ++c2[buf[i++] - 'A'];
		if (sim(c1, c2)) count++;
	}
	printf("%d\n", count);
	return 0;
}