프로그래머스 17677: 뉴스 클러스터링 (2018 카카오 공채 1차)

#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm> // sort, min
using namespace std;

bool cmp(pair<string, int> a, pair<string, int> b) {
	return a.first < b.first;
}

vector< pair < string, int> > createSubstr(string str) {
	unordered_map<string, int> umap;
	int i, size = str.size();
	string tmp = "";

	for (i = 0; i < size - 1; i++) {
		tmp = "";

		// 기타 공백이나 숫자, 특수 문자가 들어있는 경우
		if (!(('a' <= str[i] && str[i] <= 'z') || ('A' <= str[i] && str[i] <= 'Z'))) continue;
		if (!(('a' <= str[i + 1] && str[i + 1] <= 'z') || ('A' <= str[i + 1] && str[i + 1] <= 'Z'))) continue;

		// 대소문자 무시: 대문자 -> 소문자
		if ('A' <= str[i] && str[i] <= 'Z') str[i] = 'a' + (str[i] - 'A');
		if ('A' <= str[i + 1] && str[i + 1] <= 'Z') str[i + 1] = 'a' + (str[i + 1] - 'A');

		tmp += str[i];
		tmp += str[i + 1];
		umap[tmp]++;
	}

	vector< pair < string, int> > v(umap.begin(), umap.end());
	sort(v.begin(), v.end(), cmp);

	return v;
}

int solution(string str1, string str2) {
	int answer = 0;
	int i, j, intersection, sum;

	// 부분 문자열 벡터 만들기
	vector< pair < string, int> > v1 = createSubstr(str1);
	vector< pair < string, int> > v2 = createSubstr(str2);

	// 교집합 구하기
	i = 0; j = 0; intersection = 0;
	while (i < v1.size() && j < v2.size()) {
		if (v1[i].first == v2[j].first) {
			intersection += min(v1[i].second, v2[j].second);
			i++;
			j++;
		}
		else if (v1[i].first < v2[j].first) i++;
		else  j++;
	}

	// 합집합 구하기
	sum = 0;
	for (i = 0; i < v1.size(); i++) sum += v1[i].second;
	for (i = 0; i < v2.size(); i++) sum += v2[i].second;
	sum -= intersection;
	if (sum == 0) return 65536;
	else return (int)((intersection * 65536) / sum);
}