[C++] 프로그래머스 뉴스 클러스터링

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

프로그래머스

풀이

두 문자열이 주어졌을 때, 각 문자열을 길이 2의 문자로 잘라 두개의 다중집합으로 만듭니다. 그 후 두개 다중집합의 자카드 유사도를 구하는 문제입니다. 단, 특수문자 공백이 포함된경우 길이 2의 문자를 만들 수 없습니다. 또한, 합집합이 공집합인 경우의 자카드 유사도는 1입니다.

 

문제에 따라 다음과 같이 알고리즘을 구성합니다.

1. 주어진 문자열을 길이 2로 잘라나갑니다. isalpha 함수를 사용해 특수문자 및 공백을 걸러내며, 결과로 나온 두 집합을 비교하기 위해 대문자 또는 소문자로 변환하여 저장합니다.

이때, map 자료 구조변수 memo1, memo2 를 사용해 각 문자가 몇 번 등장했는지 저장합니다.

또한, 등장한 모든 길이 2의 문자열을 중복없이 저장하기 위한 set 자료구조 변수 s를 사용해 문자를 저장해줍니다.

 

2. set 자료구조에 지금까지 등장한 모든 길이 2의 문자열을 저장했기 때문에, 변수 s를 순회하며 다중집합에서의 교집합과 합집합 갯수를 구하면 됩니다.

 

3. 교집합과 합집합 갯수는 문제에서 주어진대로, 

• 교집합 = min(다중집합 memo1 에서 현재 문자열 i의 개수, 다중집합 memo2에서 현재 문자열 i의 개수)
• 합집합 = max(다중집합 memo1 에서 현재 문자열 i의 개수, 다중집합 memo2에서 현재 문자열 i의 개수)

입니다.

 

코드

#include <string>
#include <iostream>
#include <cmath>
#include <cctype>
#include <vector>
#include <map>
#include <set>

using namespace std;

int solution(string str1, string str2) {
    int answer = 0;

    string memo="";
    int count=0;
    
    map<string, int> memo1, memo2;
    set<string> s;
    
    for(int i=0;i<str1.length();i++){
        if(isalpha(str1[i])){
            str1[i]=toupper(str1[i]);
            memo+=str1[i];
        }
        else{
           memo="";
        }
        if(memo.length()==2){
            memo1[memo]++;
            s.insert(memo);
            memo=str1[i];
        }
    }
    
    memo="";
    
    for(int i=0;i<str2.length();i++){
        if(isalpha(str2[i])){
            str2[i]=toupper(str2[i]);
            memo+=str2[i];
        }
        else{
           memo="";
        }
        if(memo.length()==2){
            memo2[memo]++;
            s.insert(memo);
            memo=str2[i];
        }
    }
    
    int common_cnt = 0;
    int union_cnt = 0;
    for (auto i : s) {
        common_cnt += min(memo1[i], memo2[i]);
        union_cnt += max(memo1[i], memo2[i]);
    }
    
    if (union_cnt == 0) 
        answer = 65536;
    else
        answer = floor((double)common_cnt / (double)union_cnt * 65536);
    
    return answer;
}