[프로그래머스/알고리즘] 뉴스 클러스터링

뉴스 클러스터링

입출력 예제

str1 : FRANCE

str2 : french

해결 방법

문제에서 2개의 문자 만들어야한다. 조합으로 만드는것이 아니라 순서대로 2글자 만드는 것이므로 for문 1개로 해당 위치와 다음 위치를 불러와서 저는 multiset에 저장했습니다. 2개의 집합을 만들어 냈으면 1번째 집합의 개수만큼 union을 더하고 2번째 집합에 대해서 1번째의 값이 속해있으면 intersaction에 더하고 없으면 union에 더하면서  풀어나가면 해결이 된다. 만약 속한게 있으면 1번째 집합에 있는 해당 값을 없애 줘야 한다.

소스 코드

#include <string>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

int solution(string str1, string str2) {

	multiset<string> sstr1;
	multiset<string> sstr2;
	for (int i = 0; i < str1.length()-1; i++) {
		string data;
		data.assign(" ", 2);
		if ((str1[i] >= 'a'&&str1[i] <= 'z')||(str1[i]>='A'&&str1[i]<='Z')) {
			if ((str1[i+1] >= 'a'&&str1[i+1] <= 'z') || (str1[i+1] >= 'A'&&str1[i+1] <= 'Z')) {
				data[0]=toupper(str1[i]);
				data[1]=toupper(str1[i + 1]);

				sstr1.insert(data);
			}
		}
	}

	for (int j = 0; j < str2.length()-1; j++) {
		string data;
		data.assign(" ", 2);
		if ((str2[j] >= 'a'&&str2[j] <= 'z') || (str2[j]>='A'&&str2[j]<='Z')) {
			if ((str2[j + 1] >= 'a'&&str2[j + 1] <= 'z') || (str2[j + 1] >= 'A'&&str2[j + 1] <= 'Z')) {
				data[0] = toupper(str2[j]);
				data[1] = toupper(str2[j + 1]);
				sstr2.insert(data);
			}
		}
	}
  	if (sstr1.size() == 0 && sstr2.size() == 0)
		return 65536;
    
	set<string>::iterator iter;
	set<string>::iterator iter2;
	int sunion = sstr1.size();
	int sintersaction = 0;

	for (iter=sstr2.begin(); iter!=sstr2.end(); ++iter) {
		iter2 = find(sstr1.begin(), sstr1.end(), *iter);
		if (iter2 != sstr1.end()) {
			sstr1.erase(iter2);
			sintersaction++;
		}
		else
			sunion++;
	}

	double answer = (double)sintersaction / sunion;
	answer *= 65536;
	return (int)answer;
}