[C++로 풀이] 뉴스 클러스터링 ⭐⭐

Date: 2021.02.10 Updated: 2021.02.10

카테고리: Programmers

📌 뉴스 클러스터링

난이도 ⭐⭐

🚀 문제

🚀 내 풀이 ⭕

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

string strLower(string str) {
    for (int i = 0; i < str.length(); ++i)
        if (str[i] >= 'A' && str[i] <= 'Z')
            str[i] = tolower(str[i]);

    return str;
}

vector<string> makeSet(string str) {
    vector<string> str_set;

    for (int i = 0; i < str.length() - 1; ) {
        string temp = str.substr(i, 2);
        if (temp[0] >= 'a' && temp[0] <= 'z') {
            if (temp[1] >= 'a' && temp[1] <= 'z') {
                str_set.push_back(temp);
                i++;
            }
            else i += 2;
        }
        else {
            if (temp[1] >= 'a' && temp[1] <= 'z') i++;
            else i += 2;
        }
    }
    return str_set;
}

int solution(string str1, string str2) {
    int answer = 0;
    int intersec = 0;   // (교집합의 원소 수)
    int uni = 0;        // (합집합의 원소 수)
    vector<string> str1_set;
    vector<string> str2_set;
    unordered_map<string, int> count;

    // 소문자로 변환
    str1 = strLower(str1);
    str2 = strLower(str2);

    // 다중 집합 만들기 (오직 영문자로 된 쌍만 반영)
    str1_set = makeSet(str1);
    str2_set = makeSet(str2);
    
    // 교집합 개수 구하는 과정
    for(int i = 0; i < str1_set.size(); i++)
        count[str1_set[i]]++;
    for(int i = 0; i < str2_set.size(); i++){
        if (count.find(str2_set[i]) != count.end()){
            if (count[str2_set[i]] == 0)
                continue;
            count[str2_set[i]]--;
            intersec++;
        }
    }
    
    // 합집합 개수 구하기
    uni = str1_set.size() + str2_set.size() - intersec;
    
    // 자카드 유사도 구하기
    if (uni == 0) answer = 65536;
    else answer = (int)((float)intersec / uni * 65536);

    return answer;
}

✈ 문자열의 대문자를 모두 소문자로 변환

string strLower(string str) {
    for (int i = 0; i < str.length(); ++i)
        if (str[i] >= 'A' && str[i] <= 'Z')
            str[i] = tolower(str[i]);

    return str;
}


//...
    // 소문자로 변환
    str1 = strLower(str1); 
    str2 = strLower(str2);

대소문자를 구분하지 않으므로 대문자들은 소문자로 변경한다. “FRANCE”는 “france”로 변경.

✈ 두 개의 문자로 이루어진 다중 집합 만들기

vector<string> makeSet(string str) {
    vector<string> str_set;

    for (int i = 0; i < str.length() - 1; ) {
        string temp = str.substr(i, 2); // 2글자씩 차례로 
        if (temp[0] >= 'a' && temp[0] <= 'z') { 
            if (temp[1] >= 'a' && temp[1] <= 'z') {  // ex) "aa"
                str_set.push_back(temp);
                i++;
            }
            else i += 2;  // ex) "a1"
        }
        else {
            if (temp[1] >= 'a' && temp[1] <= 'z') i++; // ex) "1a"
            else i += 2;  // ex) "11"
        }
    }
    return str_set;
}

//...
    vector<string> str1_set;
    vector<string> str2_set;

    // 다중 집합 만들기 (오직 영문자로 된 쌍만 반영)
    str1_set = makeSet(str1);
    str2_set = makeSet(str2);

“aa1+aa2”는 {“aa”, “aa”, “aa”} 로 만들 수 있다. “france”는 {“fr”, “ra”, “an”, “nc”, “ce”} 를 만들 수 있다.

✈ 교집합의 개수 구하기

    unordered_map<string, int> count;

    // 교집합 개수 구하는 과정
    for(int i = 0; i < str1_set.size(); i++)
        count[str1_set[i]]++;
    for(int i = 0; i < str2_set.size(); i++){
        if (count.find(str2_set[i]) != count.end()){
            if (count[str2_set[i]] == 0)
                continue;
            count[str2_set[i]]--;
            intersec++;
        }
    }

첫 번째 문자열 집합의 원소들을 모두 count 맵에 추가한다. 그리고 Value는 등장한 횟수로 카운팅.
- {“aa”, “aa”, “aa”, “ab”} 의 경우 count[“aa”] = 3, count[“ab”] = 1 이 된다.
두 번째 문자열 집합의 원소들은 첫 번째 문자열 집합의 원소들로 추가한 count 맵에 해당 원소들이 있는지를 확인한다. (값이 1 이상이어야 함)
- 있다면 교집합이므로 교집합 개수를 카운팅하고 count 맵의 value를 1 감소시킨다.
  - 첫 번째 문자열 집합이 {“aa”, “aa”} 이고 (count["aa"] = 2) 두 번째 문자열 집합이 {“aa”, “aa”, “aa”, “an”} 이라면, 이 두번째 집합의 세 번째 “aa”를 검사할 땐 count["aa"] = 0 인 상태일 것이므로 세 번째 “aa” 는 교집합 대상이 아니다.

✈ 합집합의 개수 구하기

uni = str1_set.size() + str2_set.size() - intersec;

n(A U B) = n(A) + n(B) - n(A 와 B의 교집합) 공식에 의하여.

✈ 자카드 유사도 구하기

    // 자카드 유사도 구하기
    if (uni == 0) answer = 65536;
    else answer = (int)((float)intersec / uni * 65536);

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

공부하는 식빵맘 👱‍♀️