[2018 kakao blind recruitment] 1차 뉴스 클러스터링

뉴스 클러스터링

문제 설명

주어지는 문자열을 2글자씩 잘라 다중 집합을 만들고 두 문자열의 다중집합의 합집합의 개수와 교집합의 개수를 구하는 문제다.

문제 풀이

소스코드 : C++

1. 문자열을 2글자씩 잘라주는 함수 makeArr
2. 두 글자 중 하나라도 알파벳이 아니면 continue
3. 두 글자 모두 소문자로 변환하고 sv에 담는다.
4. 위 과정 반복 후 반환
5. 변환한 두 벡터 모두 비어있다면 65536을 반환하고 종료
6. sv에 sv2를 복제한다.
7. 만약 sv에 sv1 값을 찾을 수 있다면 -> 교집합, answer++
8. answer는 교집합의 개수이고 sv1 + sv2 - answer는 합집합의 개수이다.
9. 교집합 / 합집합 * 65536을 반환한다.

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

using namespace std;

const int MUL = 65536;


vector <string> makeArr(string str){
    vector<string> sv;
    string sub;

    for(int i = 0; i < str.length()-1; i++){
        if(!isalpha(str[i]) || !isalpha(str[i+1])) continue;
        str[i] = tolower(str[i]);
        str[i+1] = tolower(str[i+1]);
        sub = str.substr(i,2);
        sv.push_back(sub);
    }
    return sv;
}
int solution(string str1, string str2) {
    int answer = 0;
    vector <string> sv1 = makeArr(str1);
    vector <string> sv2 = makeArr(str2);
    vector <string> sv = sv2;

    if(!sv1.size() && !sv2.size()) return MUL;

    for(int i = 0; i < sv1.size(); i++){
        auto itr = find(sv.begin(), sv.end(), sv1[i]);
        if(itr != sv.end()){
            sv.erase(itr);
            answer++;
        }
    }
    return MUL * ((double)answer/(double)(sv1.size()+sv2.size()-answer));
}

 

소스코드 : Python

항상 느끼지만 한 줄 코딩... 신세계다.

makeArr 와 같은 방식으로 문자열을 잘라주고

합집합의 개수는 다중집합이 아닌 집합(set) 처리를 해주었을 때의 합집합, 교집합 안의 원소들을 하나씩 꺼내어

합집합은 개수가 많은 것들을 더해주고, 교집합은 개수가 적은 것들을 더해주어 답을 반환한다.

def solution(str1, str2):
    MUL = 65536
    str1 = [str1[i:i+2].lower() for i in range(0,len(str1)-1) if str1[i:i+2].isalpha()]
    str2 = [str2[i:i+2].lower() for i in range(0,len(str2)-1) if str2[i:i+2].isalpha()]
    if len(str1)==0 and len(str2)==0: return MUL

    union = sum([max(str1.count(u), str2.count(u)) for u in set(str1) | set(str2)])
    intersec = sum([min(str1.count(i), str2.count(i)) for i in set(str1) & set(str2)])

    return int(intersec/union*MUL)