[BOJ 2607 // C++] 비슷한 단어

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 2607번 문제인 비슷한 단어이다.
문제는 아래 링크를 확인하자.

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

2607번: 비슷한 단어

단어 X를 단어 Y로 바꿀 때, 개수가 증가한 알파벳들의 그 증가한 개수의 총합 overcnt와 개수가 감소한 알파벳들의 그 감소한 개수의 총합 undercnt을 구해보자.

 

두 단어의 구성이 같다면 overcnt=0, undercnt=0일 것이고, 한 문자가 더해졌다면 overcnt=1, undercnt=0일 것이다. 한 문자를 뺐다면 overcnt=0, undercnt=1일 것이고, 한 문자 하나를 다른 문자 하나로 바꿨다면 overcnt=1,undercnt=1일 것이다. 이 외의 경우 두 단어는 비슷한 단어가 될 수 없다.

 

이를 이용해 비슷한 단어의 개수를 세어 문제를 해결하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <cstring>
using namespace std;

int cnt1[128];
int cnt2[128];
int ans = 0;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N; cin >> N;
	string s; cin >> s;
	for (auto& l : s) cnt1[l]++;

	for (int _ = 1; _ < N; _++) {
		memset(cnt2, 0, sizeof(cnt2));
		cin >> s;
		for (auto& l : s)cnt2[l]++;
		int overcnt = 0, undercnt = 0;
		for (int i = 'A'; i <= 'Z'; i++) {
			if (cnt1[i] < cnt2[i]) overcnt += cnt2[i] - cnt1[i];
			else if (cnt1[i] > cnt2[i]) undercnt += cnt1[i] - cnt2[i];
		}
		if (overcnt < 2 && undercnt < 2) ans++;
	}

	cout << ans;
}