[2017_Blind_Kakao] 뉴스 클러스터링

https://programmers.co.kr/learn/courses/30/lessons/17677

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

 

문제에서 말하는 자카드 유사도에 대해 제대로 이해해야 풀 수 있는 문제.

 

잘못 이해하면 디버깅하다 시간만 버릴수 있다..

 

나같은 경우도 처음에 문제를 잘못 이해해서 한참 디버깅했지만, 금방 해결방법을 찾아서 문제를 풀 수 있었다.

 

헷갈릴만한 부분은 "기타 공백이나 숫자, 특수 문자가 들어있는 경우는 그 글자 쌍을 버린다." 이부분..

 

처음 문제를 풀 때 애초에 공백, 숫자, 특수 문자를 고려하지 않고 교집합, 합집합을 구했다..

 

문제의 정확한 해결방법은 공백, 숫자, 특수 문자를 포함해서 글자 쌍을 만든뒤 이것들이 들어가 있는 것들을 버리고 교집합, 합집합을 만들어주면 된다.

 

나머지는 평이하게 이해할 수 있다.

 

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

long long solution(string str1, string str2) {
    long long answer = 0;
    
   string str1_s, str2_s;

	for (int i = 0; i < str1.length(); i++) {
		if (str1[i] >= 65 && str1[i]<=90) str1_s += str1[i];
		else if (str1[i] >= 97 && str1[i] <= 122) str1_s += (str1[i] - 32);
		else str1_s += str1[i];
	}

	for (int i = 0; i < str2.length(); i++) {
		if (str2[i] >= 65 && str2[i] <= 90) str2_s += str2[i];
		else if (str2[i] >= 97 && str2[i] <= 122) str2_s += (str2[i] - 32);
		else str2_s += str2[i];
	}

	vector<string> str1_set, str2_set;
	int i = 0, j = 1;

	while (1) {
		if (j >= str1_s.length()) break;

		string temp1;
		
		if (str1_s[i] >=65 && str1_s[i] <= 90 && str1_s[j] >= 65 && str1_s[j] <= 90) {
			temp1 += str1_s[i];
			temp1 += str1_s[j];

			str1_set.push_back(temp1);
		}

		i++, j++;
	}



	i = 0, j = 1;
	while (1) {
		if (j >= str2_s.length()) break;
		
		string temp2;
		
		if (str2_s[i] >= 65 && str2_s[i] <= 90 && str2_s[j] >= 65 && str2_s[j] <= 90) {
			temp2 += str2_s[i];
			temp2 += str2_s[j];

			str2_set.push_back(temp2);
		}
		
		i++, j++;
	}

	if (str1_set.size() == 0 && str2_set.size() == 0) answer = 65536;

	else {
		vector<string> and_set, union_set;

		sort(str1_set.begin(), str1_set.end());
		sort(str2_set.begin(), str2_set.end());

		//교집합
		i = 0, j = 0;
		while (i != str1_set.size() && j != str2_set.size()) {
			if (str1_set[i] == str2_set[j]) {
				and_set.push_back(str1_set[i]);
				i++, j++;
			}
			else {
				if (str1_set[i] > str2_set[j]) {
					j++;
				}
				else
					i++;
			}
		}

		//합집합
		for (int i = 0; i < str1_set.size(); i++) {
			union_set.push_back(str1_set[i]);
		}
		for (int i = 0; i < str2_set.size(); i++) {
			union_set.push_back(str2_set[i]);
		}

		for (int i = 0; i < and_set.size(); i++) {
			for (int j = 0; j < union_set.size(); j++) {
				if (and_set[i] != "" && union_set[j] != "" && and_set[i] == union_set[j]) {
					union_set[j] = "";
					and_set[i] = "";
				}
			}
		}

		int down_val = 0;
		for (int i = 0; i < union_set.size(); i++) {
			if (union_set[i] != "") {
				down_val += 1;
			}
		}

		if (down_val == 0) answer = 1;
		else answer = ((and_set.size() * 65536) / down_val);
	}
    
    return answer;
}