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

문제 설명

/* 중략 */
자카드 유사도는 집합 간의 유사도를 검사하는 여러 방법 중의 하나로 알려져 있다. 두 집합 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로 정의한다.

/* 중략 */

입력으로 들어온 두 문자열의 자카드 유사도를 출력한다. 유사도 값은 0에서 1 사이의 실수이므로, 이를 다루기 쉽도록 65536을 곱한 후에 소수점 아래를 버리고 정수부만 출력한다.

제한사항

• 입력으로는 str1과 str2의 두 문자열이 들어온다. 각 문자열의 길이는 2 이상, 1,000 이하이다.
• 입력으로 들어온 문자열은 두 글자씩 끊어서 다중집합의 원소로 만든다. 이때 영문자로 된 글자 쌍만 유효하고, 기타 공백이나 숫자, 특수 문자가 들어있는 경우는 그 글자 쌍을 버린다. 예를 들어 ab+가 입력으로 들어오면, ab만 다중집합의 원소로 삼고, b+는 버린다.
• 다중집합 원소 사이를 비교할 때, 대문자와 소문자의 차이는 무시한다. AB와 Ab, ab는 같은 원소로 취급한다.

---

풀이

55분
각 스트링에 대한 map을 선언하고, 각 스트링에서 발생하는 글자쌍과 발생 빈도를 저장한다. 그리고 발생한 모든 글자쌍을 돌면서, 발생 빈도가 양쪽에서 모두 1이상인 경우 교집합이므로 분자에 작은값, 분모에 큰 값을 더해주고, 아닌 경우에는 교집합의 여집합이므로 분모에 더해주었다. 방식 자체는 어렵지 않게 떠올렸는데, 코드가 아주 조금 지저분해지는 과정에서 인덱싱이나 부호를 실수하게 되었다.

코드

// 11:33 ~ 12:27
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <iostream>

using namespace std;

int solution(string str1, string str2) {
    int joint =0, total = 0;
    
    map<string,int> m1;
    map<string,int> m2;
    set<string> s;
    
    for(int i =0; i < str1.length() - 1; ++i){
        if(str1[i] >= 'A' && str1[i] <= 'Z') str1[i] = str1[i] - 'A' + 'a';
        if(str1[i+1] >= 'A' && str1[i+1] <= 'Z') str1[i + 1] = str1[i + 1] - 'A' + 'a';
        if(str1[i] >= 'a' && str1[i] <= 'z' && str1[i+1] >= 'a' && str1[i+1] <= 'z'){
            m1[str1.substr(i,2)]++;
            s.insert(str1.substr(i,2));
        }
    }
    
    for(int i =0; i < str2.length() - 1; ++i){
        if(str2[i] >= 'A' && str2[i] <= 'Z') str2[i] = str2[i] - 'A' + 'a';
        if(str2[i+1] >= 'A' && str2[i+1] <= 'Z') str2[i + 1] = str2[i + 1] - 'A' + 'a';
        if(str2[i] >= 'a' && str2[i] <= 'z' && str2[i+1] >= 'a' && str2[i+1] <= 'z'){
            m2[str2.substr(i,2)]++;
            s.insert(str2.substr(i,2));
        }
    }
    
    int m1_cnt,m2_cnt;
    for(string str : s){
        m1_cnt =0;m2_cnt=0;
        if(m1.find(str) != m1.end()) m1_cnt = m1[str];
        if(m2.find(str) != m2.end()) m2_cnt = m2[str];
        if(m1_cnt != 0 && m2_cnt != 0){
            joint += min(m1_cnt,m2_cnt);
            total += max(m1_cnt,m2_cnt);
        }
        else{
            total += m1_cnt + m2_cnt;
        }
    }
    if(total == 0) return 65536;
    return joint*65536/total;
}