[프로그래머스_레벨2] 뉴스 클러스터링 (2018 KAKAO BLIND RECRUIT.)

https://programmers.co.kr/learn/courses/30/lessons/17677

코딩테스트 연습 - [1차] 뉴스 클러스터링 | 프로그래머스

재밌는 문제다.

 

알파벳으로 이루어진 벡터 두 개에서 교집합과 합집합의 성질을 이용해 '자카드 유사도'라는 수치를 구하는 문제다.

C++ <map> 라이브러리를 활용해 풀었는데, 벡터에 길이가 2인 문자열들을 저장해두고 추후에 벡터를 루프돌면서 해당 문자열을 'key'삼아 'value'를 ++해주는 것이 중요하다.

 

이 과정을 거친 뒤 두 map 중 어느 하나를 잡아 순회하면서 상대 map에 동일 key의 value와 최소값을 구해 교집합에 들어갈 원소의 수를 더해주고 이를 반복하면 총 교집합의 원소의 수가 나오게 된다.

 

전체 집합의 크기에서 교집합의 수를 뺀 것이 합집합과 동일한 성질을 이용하면 위에서 구한 교집합을 이용해 합집합의 크기도 쉽게 구할 수 있고, 이를 통해 '자카드 유사도'를 계산할 수 있다.

 

최종적으로 mul 로 정의해둔 값과 '자카드 유사도'를 곱해 정수부를 반환하면 된다.

#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <iostream>
#define mul 65536
using namespace std;
 
int solution(string str1, string str2) {
    int answer;
    double jacard;
 
    vector<string> v1, v2;
    for (int i = 0; i<str1.length() - 1; i++){
        // 알파벳 아닌 것들 모두 제외.
        if (!(('a' <= str1[i] && str1[i] <= 'z') || ('A' <= str1[i] && str1[i] <= 'Z'))){
            continue;
        }
        else if (!(('a' <= str1[i + 1] && str1[i + 1] <= 'z') || ('A' <= str1[i + 1] && str1[i + 1] <= 'Z'))){
            continue;
        }
        // 모두 대문자로 바꿈
        string cur = str1.substr(i, 2);
        for (int j = 0; j<2; j++)
            if ('a' <= cur[j] && cur[j] <= 'z') cur[j] -= ('a' - 'A');
        v1.push_back(cur);
    }
 
    for (int i = 0; i<str2.length() - 1; i++){
        if (!(('a' <= str2[i] && str2[i] <= 'z') || ('A' <= str2[i] && str2[i] <= 'Z'))){
            continue;
        }
        else if (!(('a' <= str2[i + 1] && str2[i + 1] <= 'z') || ('A' <= str2[i + 1] && str2[i + 1] <= 'Z'))){
            continue;
        }
        // 모두 대문자로 저장
        string cur = str2.substr(i, 2);
        for (int j = 0; j<2; j++)
            if ('a' <= cur[j] && cur[j] <= 'z') cur[j] -= ('a' - 'A'); // 소문자면 대문자로.
        v2.push_back(cur);
    }
    if (v1.empty() && v2.empty()) return mul; // 아무것도 안들어간 경우.
 
    map<string, int> m1, m2;
    for (int i = 0; i<v1.size(); i++) m1[v1[i]]++;
    for (int i = 0; i<v2.size(); i++) m2[v2[i]]++;
    double gyo = 0, hap, whole;
    whole = (double)(v1.size() + v2.size());
    // gyo 구하기 -> 끝
    for (map<string, int>::iterator iter = m1.begin(); iter != m1.end(); iter++){
        string this_str = iter->first;
        int m1_cnt = iter->second;
        int m2_cnt = m2[this_str];
        int min_val = min(m1_cnt, m2_cnt);
        if (min_val > 0) gyo += (double)min_val;
    }
    hap = whole - gyo; // 3 = 5 - 2 (tc#3)
    //cout << gyo << " " << hap << " " << whole << '\n';
    jacard = gyo / hap;
    answer = (int)(jacard*mul);
    return answer;
}