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

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

프로그래머스

 

#include <string>
#include <cctype>
#include <unordered_map>
using namespace std;

unordered_map<string,int> make_map(const string& str)
{
    unordered_map<string,int> um;
    
    for(int i=0;i<str.length()-1;i++)
    {
        if(isalpha(str[i])&&isalpha(str[i+1]))
        {
            string s = {(char)tolower(str[i]),(char)tolower(str[i+1])};
            um[s]++;
        }
    }
    return um;
}

int solution(string str1, string str2) {

    unordered_map<string,int> um1 = make_map(str1);
    unordered_map<string,int> um2 = make_map(str2);    
    
    int intersectionSize=0;
    int unionSize=0;
    
    for(auto& item : um1)
    {
        auto it = um2.find(item.first);
        // 찾았다면 
        if(it!=um2.end())
        {
            intersectionSize += min(item.second,um2[item.first]);
            unionSize += max(item.second,um2[item.first]);
            um2.erase(it);
        }
        else
            unionSize += item.second;
    }
    
    for(const auto& item : um2)
    {
        unionSize+=item.second;
    }
    if(unionSize==0)return 65536;
    return static_cast<int>(static_cast<double>(intersectionSize)/unionSize*65536);
}

 

이 문제를 풀 때, 교집합과 합집합을 알고싶으면 데이터를 많이 검색해야하기 때문에 해시테이블을 사용하는 자료구조를 사용해겠다고 생각했다. 정렬은 필요없으니 unordered_map 을 자료구조로 선택했다.

 

코드가 중복되니 make_map 함수를 따로 만들어 2개의 map을 생성한다.

 

그리고 하나의 map을 순회하며 그 원소가 다른 map에 존재한다면 교집합의 원소가 된다. 

map에는 키로 string이 값으로 그 string이 몇개였는지가 있기 때문에 두개의 map중 값이 더 작은 것을 교집합의 원소 수에 더한다. 

합집합의 개수에는 같은 이유로 더 큰 값을 더한다. 

그리고 다른 map의 원소를 삭제하는데 계산한 것을 제거하기 위함이다.

 

for문을 마치고 순회하지 않았던 map을 순회하며 값을 전부 합집합에 더한다. 

먼저 순회한 map의 string과 겹치지않는 것들만 남아있기때문이다. 

 

마지막 계산에서는 형변환으로 static_cast를 사용했다. 

c스타일의 형변환보다 안전하며, 가독성도 좋기 때문이다.