[PS 백준 - 1.12] 2607번: 비슷한 단어

문제 정보

백준 2607번 - 바로가기

• 난이도: 실버 4
• 알고리즘: 문자열

---

코멘트

블로그 해설을 참고하여 맞췄다. 처음에 접근한 방식이 너무 복잡해서 결국 내 힘으로 풀어내지 못했다.

나는 처음에 multiset을 이용하여 단어들을 저장한 뒤, mismatch 알고리즘으로 다른 부분을 잡아내려고 했다. 근데 이러면 잡아낸 단어를 삭제하고 다시 한번 더 돌려야 되는 번거로움이 있고, mismatch 결과로 나온 pair 객체에 포인터로 접근하려니 자꾸 오류가 떴다.

그래서 결국 블로그 글을 봤는데 이 문제는 "알파벳 찾기" 문제의 연장선상에 있는 문제라는걸 깨닫게 되었다. 굳이 multiset으로 할 필요 없이 알파벳이 나온 횟수만 가지고 풀어도 됐다. 이 아이디어를 적용하니 엄청 간편하게 풀렸다 ㅠㅠ

---

소스 코드

#include <iostream>
#include <cmath>

using namespace std;

int main() {
	cin.tie(NULL);
	cout.tie(NULL);
	std::ios::sync_with_stdio(false);

	int n, count = 0;
	cin >> n;

	string answer;
	string temp;

	cin >> answer;
	int arr1[26] = { 0 };
	int arr2[26] = { 0 };

	for (int i = 0; i < answer.size(); i++) {
		arr1[answer[i] - 'A']++;
	}
	
	for (int i = 0; i < n - 1; i++) {
		cin >> temp;
		for (int j = 0; j < 26; j++) arr2[j] = 0;

		for (int j = 0; j < temp.size(); j++) {
			arr2[temp[j] - 'A']++;
		}

		int diff = 0;
		for (int j = 0; j < 26; j++) {
			diff += abs(arr1[j] - arr2[j]);
		}

		if (answer.size() == temp.size()) {
			if (diff < 3) count++;
		}
		else {
			if (diff < 2) count++;
		}
	}
	cout << count;

}