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

---

🔗 문제 링크

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

프로그래머스

---

728x90

👩‍💻 코드

#include <string>
#include <vector>
#include <algorithm>
#include <cctype>
#include <iostream>
#include <map>

using namespace std;

vector<string> createMultiSet(string str){
    vector<string> v;
    
    transform(str.begin(), str.end(), str.begin(), ::tolower);
    
    for(int i=0; i<str.size()-1; i++){
        if(isalpha(str[i]) && isalpha(str[i+1])){
            v.push_back(str.substr(i, 2));
        }
    }
    
    return v;
}

map<string, int> createMap(vector<string> multiSet){
    map<string, int> freqMap;
    
    for(string set : multiSet){
        freqMap[set]++;
    }
    
    return freqMap;
}

int solution(string str1, string str2) {
    vector<string> multiSet1 = createMultiSet(str1);
    vector<string> multiSet2 = createMultiSet(str2);
    vector<string> intersection;
    vector<string> unionSet;
    map<string, int> freq1 = createMap(multiSet1);
    map<string, int> freq2 = createMap(multiSet2);
    
    for(auto f : freq1){
        if(freq2.count(f.first) > 0){
            int count = min(f.second, freq2[f.first]);
            for(int i=0; i<count; i++){
                intersection.push_back(f.first);
            }
        }
    }
    
    for(auto f : freq1){
        int count = max(f.second, freq2[f.first]);
        for(int i=0; i<count; i++){
            unionSet.push_back(f.first);
        }
    }
    
    for(auto f : freq2){
        if(freq1.count(f.first) == 0){
            for(int i=0; i<f.second; i++){
                unionSet.push_back(f.first);
            }
        }
    }
    
    if(unionSet.empty()){
        return 65536;
    }
    
    double answer = (double) intersection.size() / unionSet.size();
    
    return static_cast<int>(answer * 65536);
}

---

📝 풀이

우선 문자열을 두 글자씩 끊어 다중 집합으로 만드는 함수(createMultiSet)를 작성하였다.

대소문자를 구분하지 않기 위해 문자열을 모두 소문자로 만든 후, 두 글자가 모두 영문자인 경우에만 집합에 추가하였다.

 

원소의 중복을 허용하기 때문에 다중 집합의 빈도수를 확인 할 수 있도록 map에 저장하고자 했다.

원소를 키값으로 가지고 빈도수를 값으로 가지는 map<string, int>을 만드는 함수(createMap)를 작성하였다.

 

첫 번째 for문은 교집합을 구하는 반복문이다.

두 다중 집합에서 동일한 원소가 나타나는 빈도 중 작은 값을 선택해야 한다.

 

두 번째 for문은 합집합을 구하는 반복문이다.

두 다중 집합에서 동일한 원소가 나타나는 빈도 중 큰 값을 선택해야 한다.

 

세 번째 for문도 마찬가지로 합집합을 구하는 반복문이다.

두 번쨰 for문에서 기준으로 사용한 다중 집합과 다른 다중 집합에만 존재하는 원소도 추가해야 한다.

 

최종적으로 0으로 나누는 예외처리를 하고 교집합에서 합집합을 나눈 값에서 정수 값에만 65536을 곱하여 답을 return.