[1차] 뉴스 클러스터링

코드

#include <string>
#include <map>
#include <algorithm>
#include <numeric>
#include <iostream>
// 12:03 ~ 01:00 
using namespace std;

int solution(string str1, string str2) {
    int answer = 0;
    map <string, int> m1;
    map <string, int> m2;
    transform(str1.begin(), str1.end(), str1.begin(), ::tolower);
    transform(str2.begin(), str2.end(), str2.begin(), ::tolower);
    /* str1에 대해 2개씩 분할해서 저장 */
    for(int i=0;i<str1.length()-1;i++)
    {
        char ch1 = str1[i];
        char ch2 = str1[i+1];
        string temp="";
        //if((ch1 >= 'a' && ch1 <= 'z') && (ch2 >= 'a' && ch2 <= 'z')){
        if(isalpha(ch1) && isalpha(ch2)){
            temp+=ch1;
            temp+=ch2;
            m1[temp]++;
        }else continue;
    }
    /* str2에 대해 2개씩 분할해서 저장 */
    for(int i=0;i<str2.length()-1;i++)
    {
        char ch1 = str2[i];
        char ch2 = str2[i+1];
        string temp="";
        //if((ch1 >= 'a' && ch1 <= 'z') && (ch2 >= 'a' && ch2 <= 'z')){
        if(isalpha(ch1) && isalpha(ch2)){
            temp+=ch1;
            temp+=ch2;
            m2[temp]++;
        }else continue;
    }
    /* 교집합 구하기 - 둘 다 있는 원소중 min개수가 교집합 개수*/
    vector<int> both;
    for(auto it1=m1.begin();it1 != m1.end();it1++){
        string s1 = it1->first;
        for(auto it2=m2.begin();it2 != m2.end();it2++){
            if(s1 == it2->first){
                both.push_back(min(it1->second, it2->second));
                break;
            }
        }
    }
    /* 합집합 구하기 - 각 문자의 max개수가 된다 */
    map<string,int> sum;
    for(auto it1=m1.begin();it1 != m1.end();it1++){
        int value = it1->second;
        if(m2[it1->first]) value = max(value,m2[it1->first]);
        sum[it1->first] = value;
    }
    for(auto it2=m2.begin();it2 != m2.end();it2++){
        int value = it2->second;
        if(m1[it2->first]) value = max(value, m1[it2->first]);
        sum[it2->first] = value;
    }
    /* 교집합 & 합집합 각 개수 구하기 */
    int cnt_both = accumulate(both.begin(), both.end(), 0);
    int cnt_sum = 0;
    for(auto it=sum.begin();it != sum.end();it++) cnt_sum += it->second;
    /* 결과 구하기 */
    int result;
    if(cnt_sum != 0) result = (cnt_both/(double)cnt_sum) * 65536;
    else result = 1*65536;
    answer = result;
    return answer;
}

• 로직
  1) 각 문자열에서 2개씩 나누어 map에 저장
  2) 교집합 구하기 : 공통으로 있는 원소 중 min개수인 것
  3) 합집합 구하기 : 원소 개수의 max 개수

• isalpha(ch)를 사용하면 알파벳인지 검사해준다!

---

[ 짧은 코드 ]

#include <bits/stdc++.h>
using namespace std;
short a, b, C[676], D[676];
int solution(string A, string B) {
    for(int i=1; i<A.size(); i++)
        if(isalpha(A[i-1]) && isalpha(A[i]))
            C[(A[i-1]&31)*26+(A[i]&31)]++;
    for(int i=1; i<B.size(); i++)
        if(isalpha(B[i-1]) && isalpha(B[i]))
            D[(B[i-1]&31)*26+(B[i]&31)]++;
    for(int i=0; i<676; i++) a+=min(C[i], D[i]), b+=max(C[i], D[i]);
    return b ? a*65536/b : 65536;
}

• map을 안쓰고 배열 or 벡터를 쓴다면?
  : 26*26크기만큼 0으로 초기화를 해준 뒤,
  문자를 숫자로 바꿔 저장해서 min, max개수로 교집합,합집합 구함
• 26*26의 빈 공간을 만든 뒤, 바로 min,max를 한 것이 핵심!