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

문제풀이 : programmers.co.kr/learn/courses/30/lessons/17677

코딩테스트 연습 - [1차] 뉴스 클러스터링

문제 유형

구현, Map

 

두 문자열의 각 두 문자씩을 분리해 Map에 원소로 넣는다.

이 풀이에서는 map<string, pair<int, int>를 사용했으며,

value에 해당하는 pair의 first에는 str1의 해당 원소 개수, second에는 str2의 해당 원소 개수를 저장했다.

이 경우, 각 원소에 대해 합집합에서 해당 원소의 개수는 max(first, second)가 될 것이고

교집합에서 해당 원소의 개수는 min(first, second)가 될 것이다.

 

이렇게 구한 각 값들을 통해 정답을 구하면 된다.

 

[코드]

#include <string>
#include <algorithm>
#include <map>
#include <iostream>
 
using namespace std;
typedef pair<int, int> p;
 
map<string, p> dict;    //value : (str1, str2)
vector<string> list;
bool alphabet[1001][2];
 
void memo(string str, int num){
    for(int i = 0; i < str.size() - 1; i++){
        string temp = str.substr(i, 2);
        if(!alphabet[i][num] || !alphabet[i + 1][num]) continue;
        
        list.push_back(temp);
        if(dict.find(temp) == dict.end()) dict.insert({temp, {0, 0}});
        if(num == 0) dict[temp].first += 1;
        else dict[temp].second += 1;
    }
}
 
string prev_action(string str, int num){
    for(int i = 0; i < str.size(); i++){
        if('a' <= str[i] && str[i] <= 'z') {
            str[i] = toupper(str[i]);
            alphabet[i][num] = true;
        }
        else if ('A' <= str[i] && str[i] <= 'Z') alphabet[i][num] = true;
    }
    return str;
}
 
int solution(string str1, string str2) {
    int answer = 0;
    
    str1 = prev_action(str1, 0);
    str2 = prev_action(str2, 1);
    memo(str1, 0);
    memo(str2, 1);
    
    if(list.empty()) return 65536;
    
    sort(list.begin(), list.end());
    list.erase(unique(list.begin(), list.end()), list.end());
    
    int unions = 0, intersection = 0;
    for(int i = 0; i < list.size(); i++){
        p val = dict[list[i]];
        unions += max(val.first, val.second);
        intersection += min(val.first, val.second);
    }
    
    double rate = (double) intersection / unions;
    answer = rate * 65536;
    
    return answer;
}