[programmers] [1차] 뉴스 클러스터링_c++
2018 KAKAO BLIND RECRUITMENT - [1차] 뉴스 클러스터링 Lv. 2
문제
자카드 유사도는 집합 간의 유사도를 검사하는 여러 방법 중의 하나로 알려져 있다.
두 집합 A, B 사이의 자카드 유사도 J(A, B)는 두 집합의 교집합 크기를 두 집합의 합집합 크기로 나눈 값으로 정의된다.
예를 들어 집합 A = {1, 2, 3}, 집합 B = {2, 3, 4}라고 할 때, 교집합 A ∩ B = {2, 3}, 합집합 A ∪ B = {1, 2, 3, 4}이 되므로,
집합 A, B 사이의 자카드 유사도 J(A, B) = 2/4 = 0.5가 된다.
집합 A와 집합 B가 모두 공집합일 경우에는 나눗셈이 정의되지 않으니 따로 J(A, B) = 1로 정의한다.
자카드 유사도는 원소의 중복을 허용하는 다중집합에 대해서 확장할 수 있다.
다중집합 A는 원소 "1"을 3개 가지고 있고, 다중집합 B는 원소 "1"을 5개 가지고 있다고 하자.
이 다중집합의 교집합 A ∩ B는 원소 "1"을 min(3, 5)인 3개, 합집합 A ∪ B는 원소 "1"을 max(3, 5)인 5개 가지게 된다.
다중집합 A = {1, 1, 2, 2, 3}, 다중집합 B = {1, 2, 2, 4, 5}라고 하면,
교집합 A ∩ B = {1, 2, 2}, 합집합 A ∪ B = {1, 1, 2, 2, 3, 4, 5}가 되므로, 자카드 유사도 J(A, B) = 3/7, 약 0.42가 된다.
이를 이용하여 문자열 사이의 유사도를 계산하는데 이용할 수 있다.
문자열 "FRANCE"와 "FRENCH"가 주어졌을 때, 이를 두 글자씩 끊어서 다중집합을 만들 수 있다.
각각 {FR, RA, AN, NC, CE}, {FR, RE, EN, NC, CH}가 되며, 교집합은 {FR, NC},
합집합은 {FR, RA, AN, NC, CE, RE, EN, CH}가 되므로,
두 문자열 사이의 자카드 유사도 J("FRANCE", "FRENCH") = 2/8 = 0.25가 된다.
입력 형식
- 입력으로는 str1과 str2의 두 문자열이 들어온다. 각 문자열의 길이는 2 이상, 1,000 이하이다.
- 입력으로 들어온 문자열은 두 글자씩 끊어서 다중집합의 원소로 만든다.
이때 영문자로 된 글자 쌍만 유효하고, 기타 공백이나 숫자, 특수 문자가 들어있는 경우는 그 글자 쌍을 버린다.
예를 들어 "ab+"가 입력으로 들어오면, "ab"만 다중집합의 원소로 삼고, "b+"는 버린다. - 다중집합 원소 사이를 비교할 때, 대문자와 소문자의 차이는 무시한다. "AB"와 "Ab", "ab"는 같 원소로 취급한다
출력 형식
입력으로 들어온 두 문자열의 자카드 유사도를 출력한다. 유사도 값은 0에서 1사이의 실수이므로, 이를 다루기 쉽도록 65536을 곱한 후에 소수점 아래를 버리고 정수부만 출력한다.
* 65536은 2의 16승
코드
#include <string>
#include <map>
using namespace std;
map<string, int> m1, m2;
bool isString(char c) {
if ('a' <= c && c <= 'z')
return true;
if ('A' <= c && c <= 'Z')
return true;
return false;
}
int solution(string str1, string str2) {
int totalcnt = 0;
for(int i = 0; i < str1.size() - 1; i++)
if (isString(str1[i]) && isString(str1[i + 1])) {
string elem = "";
elem += tolower(str1[i]);
elem += tolower(str1[i + 1]);
if (m1.find(elem) != m1.end())
m1[elem]++;
else
m1.insert({elem, 1});
totalcnt++;
}
for(int i = 0; i < str2.size() - 1; i++)
if (isString(str2[i]) && isString(str2[i + 1])) {
string elem = "";
elem += tolower(str2[i]);
elem += tolower(str2[i + 1]);
if (m2.find(elem) != m2.end())
m2[elem]++;
else
m2.insert({elem, 1});
totalcnt++;
}
if (m1.size() > m2.size()) {
map<string, int> tmp = m1;
m1 = m2;
m2 = tmp;
}
map<string, int>::const_iterator it, target;
int inter = 0;
for(it = m1.begin(); it != m1.end(); it++) {
target = m2.find(it->first);
if (target != m2.end()) {
if (target->second > it->second)
inter += it->second;
else
inter += target->second;
}
}
double uni = totalcnt - inter;
if (uni == 0)
return 65536;
return inter / uni * 65536;
}
* char 가 문자인지 확인하는 함수(직접 구현했지만 <cctype>헤더의 isalpha함수를 사용할 수 있다)
* 문자 2개를 각각 문자인지 확인한 후 tolower함수를 사용해 소문자의 문자열로 변환한다
* key가 문자열이고 value를 개수로 갖는 map을 사용한다
* 문자 2개가 알파벳이면 tolower함수를 사용해 소문자의 문자열을 만든다
* 이 문자열이 map에 존재하는 key이면 value를 증가시키고 존재하지 않으면 새로 만든다
* map은 str1, str2 각각 하나씩 갖는데 사이즈가 큰 map을 map1으로 오게 한다
* map1을 순회하면서 map1이랑 map2이 같은 key를 갖고 있는지 확인 후 각각의 value를 비교하여 작은 값을 inter에 추가한다
* inter는 교집합의 개수이고 totalcnt는 map1과 map2의 전체 원소의 개수이다
* uni는 합집합의 개수인데 totalcnt에서 inter를 뺀 값이다 inter이 정수이므로 나누었을 때 double형으로 받기 위해 double 형이다
* 0으로 나누게 되면 에러가 발생하므로 0일 경우에 65536을 바로 반환
* 그렇지 않은 경우 문제에서 요구하는 것과 같이 inter / uni * 65536을 반환한다