[1차]뉴스 클러스터링(2018 카카오 블라인드 채용)

문제 링크

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

 

 

 

풀이

처음에는 솔루션 함수에다가 다 짜다가 너무 길어져 중복되는 것은 함수로 뺐다.

ex() 함수는 큐를 이용하여 2글자씩 소문자로 바꿔서 넣는 역할을 한다.(물론 예외처리 다했다.)

그리고 toLower() 함수는 소문자로 바꾸는 STL을 몰라서 일단 그 자리에서 직접 만든 것이다.

그리고 algorithm에 있는 set_union함수와 set_intersection함수를 이용하여 자카드 유사도를 구하였다.

 

풀이 요약

1) ex() 함수로 두 자씩 vector 컨테이너에 집어 넣음(모두 소문자, 예외처리 완벽)

2) algorithm 클래스의 set_union 함수와 set_intersection함수를 이용하여 vector를 합친 후,

vector.size()를 통해서 자카드 유사도를 구함.

 

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

char toLower(char c)
{
    if(c>='A' && c<='Z') return c + ('a' - 'A');
    else return c;
}

void ex(string str, vector<string>& v)
{
    queue<char> q;
    for(int i=0; i<str.length(); i++)
    {
        char c = toLower(str[i]);
        if(c >= 'a' && c <= 'z') q.push(c);
        else if(!q.empty()) q.pop();
        if(q.size() == 2)
        {
            string s = "";
            s+= q.front();
            s+= q.back();
            v.push_back(s);
            q.pop();
        }
    }
    
}
// 교집합 크기/합집합 크기
int solution(string str1, string str2) {
    int answer = 0;
    vector<string> v1;
    vector<string> v2;
    
    ex(str1, v1);
    ex(str2, v2);

    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());
    
    vector<string> v3(v1.size()+v2.size());
    vector<string> v4(v1.size()+v2.size());
    
    auto iter1 = set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
    v3.resize(iter1 - v3.begin());
    auto iter2 = set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), v4.begin());
    v4.resize(iter2 - v4.begin());
    
    // for(auto e:v1) cout<<e<<", ";
    // cout<<endl;
    // for(auto e:v2) cout<<e<<", ";
    // cout<<endl;
    
    // cout<<v4.size()<< ", "<<v3.size()<<endl;
    if(v3.empty() && v4.empty()) answer = 65536;
    else answer = (double)v4.size() / v3.size() * 65536;
    
    return answer;
}