programmers [1차] 뉴스 클러스터링 c++

programmers.co.kr/learn/courses/30/lessons/17677

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

2018 카카오 블라인드 리쿠르먼트에서 출제된 level2 뉴스 클러스터링 입니다.

문제에서 요구하는대로 '구현'할 수 있는지 묻는 문제였습니다.

 

범위가 작긴 하지만 마구잡이로 순차검색하는 것 보다는

평소 익숙해지기 위해 이분탐색을 사용하여 문자열을 검색하였습니다.

순차로 검색하셔도 효율성을 따지지 않기 때문에 문제되지는 않을 것 같습니다.

 

교집합, 합집합을 만들 때에는 set을 사용해서 이미 탐색한 단어인지 확인했습니다.

 

#include <string>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

int lowerbound(vector<string> v, string str){
    int s = 0, e = v.size();
    int m;
    while(s<e){
        m = (s+e)/2;
        if(v[m] >= str) e = m;
        else s = m+1;
    }
    return e;
}

int upperbound(vector<string> v, string str){
    int s = 0, e = v.size();
    int m;
    while(s<e){
        m = (s+e)/2;
        if(v[m]>str) e = m;
        else s = m+1;
    }
    return e;
}

vector<string> getString(string str){
    vector<string> res;
    string temp;
    for(int i = 0; i<str.size()-1; i++){
        char ch1 = str[i];
        char ch2 = str[i+1];
        if(!((ch1>='a'&&ch1<='z')||(ch1>='A'&&ch1<='Z'))) continue;
        if(!((ch2>='a'&&ch2<='z')||(ch2>='A'&&ch2<='Z'))) continue;
        ch1 = tolower(ch1);
        ch2 = tolower(ch2);
        temp = ""; temp += ch1; temp += ch2;
        res.push_back(temp);
    }
    return res;
}

int solution(string str1, string str2) {
    
    vector<string> f = getString(str1);
    vector<string> s = getString(str2);
    
    if(f.size() == 0 && s.size() == 0) return 65536;
    
    // make union, difference
    
    sort(f.begin(), f.end());
    sort(s.begin(), s.end());
    int uni = 0;
    int diff = 0;
    set<string> visit;
    
    for(int i = 0; i<f.size(); i++){
        if(visit.find(f[i]) == visit.end()){
            visit.insert(f[i]);
            int fleft = lowerbound(f, f[i]);
            int fright = upperbound(f, f[i]);
            int sleft = lowerbound(s, f[i]);
            int sright = upperbound(s, f[i]);
            if(sright == sleft){ // difference
                diff += fright-fleft;
            }
            else{ // union & difference
                int uniSize = min(fright-fleft, sright-sleft);
                int diffSize = max(fright-fleft, sright-sleft);
                uni += uniSize;
                diff += diffSize;
            }
        }
    }
    
    for(int i = 0; i<s.size(); i++){
        if(visit.find(s[i]) == visit.end()){
            visit.insert(s[i]);
            int fleft = lowerbound(f, s[i]);
            int fright = upperbound(f, s[i]);
            int sleft = lowerbound(s, s[i]);
            int sright = upperbound(s, s[i]);
            if(fright == fleft){ // difference
                diff += sright-sleft;
            }
            else{ // union & difference
                int uniSize = min(fright-fleft, sright-sleft);
                int diffSize = max(fright-fleft, sright-sleft);
                uni += uniSize;
                diff += diffSize;
            }
        }
    }
    
    int answer = ((double)uni/diff)*65536;
    
    return answer;
}