[프로그래머스 - 구현] 뉴스 클러스터링 (for kakao)

[프로그래머스 - 구현] 뉴스 클러스터링

---

📄 [구현] 뉴스 클러스터링 C++ Source Code

#include <set>
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

/*	ⓐ
	자카드 유사도는 집합 간의 유사도를 검사하는 여러 방법 중의 하나로 알려져 있다.
	두 집합 A, B 사이의 자카드 유사도 J(A, B)는 두 집합의 교집합 크기를 두 집합의 합집합 크기로 나눈 값으로 정의된다.
*/

/*	ⓑ
	입력으로 들어온 문자열은 두 글자씩 끊어서 다중집합의 원소로 만든다.
	이때 영문자로 된 글자 쌍만 유효하고, 기타 공백이나 숫자, 특수 문자가 들어있는 경우는 그 글자 쌍을 버린다.
	예를 들어 ab+가 입력으로 들어오면, ab만 다중집합의 원소로 삼고, b+는 버린다.
*/

const bool checkAlpabat(const char letter) {
	return letter >= 65 && letter <= 90;
}

multiset<string> split(const string str) {

	multiset<string> result;

	for (int index = 0; index < str.size() - 1; index++) {

		// 영문자로 된 글자 쌍만 유효하고, 기타 공백이나 숫자, 특수 문자가 들어있는 경우는 그 글자 쌍을 버린다.
		if (!checkAlpabat(str[index]) || !checkAlpabat(str[index + 1])) { continue; }

		string letter;
		letter += str[index];
		letter += str[index + 1];

		result.insert(letter);
	}

	return result;
}

int solution(string str1, string str2) {

	std::transform(str1.begin(), str1.end(), str1.begin(), ::toupper);
	std::transform(str2.begin(), str2.end(), str2.begin(), ::toupper);

	multiset<string> str1_vec = split(str1);
	multiset<string> str2_vec = split(str2);

	vector<string> union_vec(str1_vec.size() + str2_vec.size());
	const auto union_begin = std::set_union(str1_vec.begin(), str1_vec.end(), str2_vec.begin(), str2_vec.end(), union_vec.begin());
	union_vec.erase(union_begin, union_vec.end());

	vector<string> intersection_vec(str1_vec.size() + str2_vec.size());
	const auto intersection_begin = std::set_intersection(str1_vec.begin(), str1_vec.end(), str2_vec.begin(), str2_vec.end(), intersection_vec.begin());
	intersection_vec.erase(intersection_begin, intersection_vec.end());

	const pair<double, double> value = make_pair(union_vec.size(), intersection_vec.size());

	int answer = 0;

	// ※ CAPTION - 집합 A와 집합 B가 모두 공집합일 경우에는 나눗셈이 정의되지 않으니 따로 J(A, B) = 1로 정의한다.
	if (value.first == 0 && value.second == 0) { answer = 65536; }
	else { answer = (value.second / value.first) * 65536; }

	// 다중집합 원소 사이를 비교할 때, 대문자와 소문자의 차이는 무시한다. AB와 Ab, ab는 같은 원소로 취급한다.

	// 유사도 값은 0에서 1 사이의 실수이므로, 이를 다루기 쉽도록 65536을 곱한 후에 소수점 아래를 버리고 정수부만 출력한다.
	return answer;
}

---

🚀 REFERENCE

코딩테스트 연습 - [1차] 뉴스 클러스터링 | 프로그래머스

ChangYeop-Yang/Study-Algorithm