[프로그래머스] 뉴스 클러스터링 2018 KAKAO BLIND RECRUITMENT

코딩테스트 연습 - [1차] 뉴스 클러스터링

먼저 각 문자열을 두 글자 단위로 나누어 각 벡터에 넣어준다.

이때, 영문자 외의 문자가 포함되면 계산에서 제외해주므로

벡터에 영문자인지 아닌지 체크해준 int값을 하나 더 넣는다.

 

벡터 A와 벡터 B가 중복되는 원소들을 각각 카운트 해준 뒤

합집합(Max)과 교집합(Min)을 계산해주고 형식에 맞게 출력해주면 끝

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

using namespace std;

int solution(string str1, string str2) {
	int answer = 0;
	vector <pair<string, int> > A;
	vector <pair<string, int> > B;
	string temp1, temp2; //두 글자 씩 끊어내기 위해

	int check1 = 0, check2 = 0; //영문자가 아닐 경우를 체크하기 위해

	if (str1[0] <= 'Z'&&str1[0] >= 'A') temp2 = str1[0] + 32; //첫 원소의 첫 글자는 따로 먼저 구해준다
	else if (str1[0] <= 'z'&&str1[0] >= 'a') temp2 = str1[0];
	else {
		temp2 = str1[0];
		check2++;
	}
	
	for (int i = 1; i<str1.size(); i++) {
		if (str1[i] <= 'Z'&&str1[i] >= 'A') {
			temp1 = temp2;
			temp1 += str1[i] + 32;
			temp2 = str1[i] + 32;
		}
		else if (str1[i] <= 'z'&&str1[i] >= 'a') {
			temp1 = temp2;
			temp1 += str1[i];
			temp2 = str1[i];
		}
		else {
			check1++;
			temp1 = temp2;
			temp1 += str1[i];
			temp2 = str1[i];
		}
		A.push_back(pair<string, int>(temp1, check1 + check2));
		check2 = check1, check1 = 0;
	}

	check1 = 0, check2 = 0;
	if (str2[0] <= 'Z'&&str2[0] >= 'A') temp2 = str2[0] + 32;
	else if (str2[0] <= 'z'&&str2[0] >= 'a') temp2 = str2[0];
	else {
		temp2 = str2[0];
		check2++;
	}

	for (int i = 1; i<str2.size(); i++) {
		if (str2[i] <= 'Z'&&str2[i] >= 'A') {
			temp1 = temp2;
			temp1 += str2[i] + 32;
			temp2 = str2[i] + 32;
		}
		else if (str2[i] <= 'z'&&str2[i] >= 'a') {
			temp1 = temp2;
			temp1 += str2[i];
			temp2 = str2[i];
		}
		else {
			check1++;
			temp1 = temp2;
			temp1 += str2[i];
			temp2 = str2[i];
		}
		B.push_back(pair<string, int>(temp1, check1 + check2));
		check2 = check1, check1 = 0;
	}

	sort(A.begin(), A.end());
	sort(B.begin(), B.end());

	int Max = 0, Min = 0, cnt1 = 1, cnt2 = 0, tot1 = 0, tot2 = 0;
	//Max는 합집합, Min은 교집합, cnt1과 cnt2는 집합 A, B의 중복원소의 개수
	//tot1과 tot2는 중복 원소를 제외한 집합 A, B의 나머지 원소의 개수

	for (int i = 0; i<A.size(); i++) { //총 원소의 개수를 영문자일 경우에만 세어놓는다
		if (A[i].second == 0) tot1++;
	}
	for (int i = 0; i<B.size(); i++) {
		if (B[i].second == 0) tot2++;
	}

	for (int i = 0; i<A.size(); i++) {
		if (A[i].second == 0) {
			if (i != A.size() - 1 && A[i].first == A[i + 1].first) { //집합 A의 중복 원소 개수 카운트
				cnt1++;
				continue;
			}
			for (int j = 0; j<B.size(); j++) {
				if (B[j].second == 0) {
					if (A[i].first == B[j].first) cnt2++; //집합 A와 중복되는 집합 B의 원소 개수 카운트
				}
			}
			if (cnt2 != 0) {
				if (cnt1>cnt2) { //cnt1과 cnt2 중 더 큰 값이 합집합에 들어가고 작은 값이 교집합에 들어간다
					Max += cnt1;
					Min += cnt2;
				}
				else {
					Max += cnt2;
					Min += cnt1;
				}
				tot1 -= cnt1; //중복되는 원소 만큼 총 개수에서 빼준다
				tot2 -= cnt2;
				if (tot1 == 0 && tot2 == 0)break;
			}
		}
		cnt1 = 1, cnt2 = 0;
	}
	Max += (tot1 + tot2);
	if (Min == 0 && Max == 0) answer = 65536;
	else {
		double res = ((double)Min / (double)Max)*(double)65536;
		answer = res;
	}
	return answer;
}