프로그래머스 - [1차] 뉴스 클러스터링

프로그래머스 - [1차] 뉴스 클러스터링

풀이 단계는 다음과 같다.

1. 주어진 문자열을 2글자씩 자른다. 단, 이 때 알파벳을 제외한 것은 제외한다.

• for-range(i = 0 ... (str.size()-1)) 까지 순회하면서 i번째 혹은 i+1째가 알파벳인지 확인한다.
• i = 0일 때, 0번째와 1번째 인덱스를 검사할텐데, 1번째가 알파벳이 아니라면 2부터 검사하면 되므로, i++을 해주고 continue를 한다.
• 대문자와 소문자를 동일하게 취급하기 위해서 소문자화 해준다.

2. 자카드 유사도를 구하기 위해 분모를 구한다.

• 분모는 두 다중집합의 합집합을 구해야한다. 이를 위해 m1, m2로 map을 2개 준비한다.
• 다중집합 A : ["aa", "aa", "bb"]라면 map["aa"]은 2를 map["bb"]는 1을 가지도록 해준다.
• m1과 m2를 더해주면 되는데, m1과 m2에 동일하게 존재하는 key의 경우 value값을 더 큰 쪽을 가지도록 해주면 된다.
• 예를 들어 A : ["aa", "aa", "bb"], B : ["aa", "bb", "bb"]의 경우 $A \cup B$의 결과는 ["aa","aa","bb","bb"]가 될 것이다. 이를 위해, A["aa"] : 2, B["aa"] : 1이므로 $A \cup B$["aa"]는 둘 중 더 큰 값인 2가 되도록 해주면 된다.
• 합집합으로 구해진 map의 value 값들을 모두 더해주면 분모가 된다.

3. 자카드 유사도를 구하기 위해 분자를 구한다.

• 분자는 두 다중집합의 교집합이다. 이를 위해 다중집합 A, B 다중집합의 map을 준비한다.
  - 굳이 map으로 안하고, 다중집합 B를 그대로 사용해도 된다. search를 빠르게 하기 위해 map을 쓴다.
• A를 앞부터 순회하면서, map에 다중집합 A의 원소가 존재하는지 체크한다.
• 만약 존재하고, 해당 Value의 값이 0보다 크다면 분자값을 1증가시킨다.
  - 0이하의 경우에는 증가시키면 안 된다.
  • 예를 들어, A : ["aa", "aa", "bb"], B : ["aa", "bb", "bb"]의 경우 $A \cap B$의 결과는 ["aa", "bb"]가 될 것이다. 즉, A의 두 번째 "aa"는 교집합에 포함되면 안된다.

4. 65536을 곱해준 결과값을 반환해준다.

• 65536은 2의 16승이므로 16만큼 left_shift 해준다.

코드는 아래와 같다.

#include <string>
#include <map>
#include <algorithm>

using namespace std;

void parse(const string &str, vector<string> &result)
{
    for(int i=0;i<str.size()-1;i++) {
        if(!isalpha(str[i]))
            continue;
        if(!isalpha(str[i+1])) {
            i++;
            continue;
        }
        string s(2, 0);
        s[0] = tolower(str[i]);
        s[1] = tolower(str[i + 1]);
        result.push_back(s);
    }
}
map<string, int> operator+ (const map<string, int> &a, const map<string, int> &b) {
    map<string, int> result;
    for(auto it : a) 
        result[it.first] = it.second;
    
    for(auto it : b) {
        if(result.find(it.first) != result.end()) 
            result[it.first] = max(result[it.first], it.second);
        else 
            result[it.first] = it.second;
    }
    return result;
}
int get_parent(const map<string, int> &m)
{
    int result = 0;
    for(auto it : m)
        result += it.second;
    
    return result;
}
int get_child(const vector<string> &a, map<string, int> &m)
{
    int result = 0;
    for(auto it : a) {
        auto entry = m.find(it);
        if(entry != m.end()) {
            if(entry->second != 0) {
                result++;
                entry->second--;
            }
        }
    }
    return result;
}
int jaccard(vector<string> s1, vector<string> s2)
{
    if(s1.empty() && s2.empty())
        return 65536;
    map<string, int> m1;
    for(auto it : s1) m1[it]++;
    map<string, int> m2;
    for(auto it : s2) m2[it]++;
    
    map<string, int>m3 = m1 + m2;
    int p = get_parent(m3);
    int c = get_child(s1, m2);
    return (int)((double)(c << 16) / (double)p);
}
int solution(string str1, string str2) {
    vector<string> s1, s2;
    parse(str1, s1);
    parse(str2, s2);
    int answer = jaccard(s1, s2);
    return answer;
}