뉴스 클러스터링

들어가는 말

인턴 시작 후 처음 제대로 푼 문제다. 저녁에 집에 오면 힘들어서 축 늘어져 있다. 그래서 공부는 아침에 하는 것으로...

아무튼 뉴스 클러스터링은 문자를 둘 씩 끊어서 교집합과 합집합을 구한 다음에 자카드 유사도를 구하는 문제다.

일단 문장을 대문자 혹은 소문자로 바꾼 다음에 substr()을 이용해 둘 씩 뜯어서 벡터에 넣어주고(이때 두 문자 모두 알파벳인 경우만 넣어준다) 합집합과 교집합을 구해주면 된다고 생각했다.

그러나 전혀 엉뚱한 곳에서 막였으니. 비교한 문자를 삭제하는 부분에서 어려움을 겪었다. erase()함수를 써야 하는데, 변수로 삭제할 데이터의 위치를 받는다고 알고 있었단 말이다. 이때 그 위치를 어떻게 구해야 하는지 모르겠는 거다. 그래서 다른 블로그를 찾아본 결과 그냥 find()해서 받은 변수를 그냥 써줬다. 옹? 이렇게 써도 괜찮은 건가? 정확해서 어떤 값을 받았는지 확인해보려 cout << tmp를 해줬는데 에러가 생겼다. 그럼 혹시... 포인터? cout << *tmp를 해주니 그제야 찾은 값이 나오는 거 아닌가. cout << &tmp를 해주면 주소가 나오고. 언제나 find()와 erase()를 쓸 때 어려움을 겪었는데, 이제야 정확하게 알게 됐다.

코드 설명

제일 먼저 문자열을 모두 소문자로 바꿔줬다.

그리고 문자를 두 개씩 떼서 tmp에 저장하는데, 이때 두 문자가 모두 알파벳 소문자인 경우에만 미리 만들어 둔 벡터에 저장한다. 문자열이 총 두개이기 때문에 두 번 해주면 된다.

다음 max에다가 만들어진 벡터들의 size() 더해준다. max는 합집합인데, 합집합의 원소의 개수는 각 집합의 원소의 개수의 합에다가 교집합의 원소의 개수를 빼주면 된다는 걸 잊지 말자. 그리고 두 벡터가 비어있을 경우 즉, 두 문자열에 알파벳 소문자가 하나도 없었을 경우에는 65536을 곱해주면 된다.

그리고 합집합을 구해주면 된다. str1_v 사이즈가 str2_v의 사이즈보다 클 경우에는 str2_v의 원소를 하나씩 가지고 와서 같은 원소가 str1_v에 있는지 확인하면 된다. 이때 find함수를 사용한다. 그리고 str1_v에 값이 있는지 확인하면 되는데, 만일 있을 경우 합집합의 크기를 늘려주고 str1_v의 해당하는 원소를 지워야 한다는 걸 잊지 말자. 나는 여기서 str2_v 원소를 지워서 첫 값이 잘못 나왔다. str2_v의 원소를 하나씩 돌면서 str1_v와 비교하는 것이기 때문에 str1_v에 있는 값을 지워줘야 한다. 그리고 또 하나! erase()함수를 쓸 때 그냥 찾았던 임시 값 tmp를 넣어줘도 된다. 왜냐하면 tmp에 값을 넣어줄 때 사용한 함수 find()는 원소를 반환하는 게 아니라 주소를 반환한다(그래서 cout << *find를 하면 find에서 찾은 값을, cout << &find를 하면 주소가 나온다). 때문에 erase()에 바로 쓸 수 있는거다.
나머지 경우들은 else를 이용해서 위의 코드에 벡터만 바꿔주면 된다.

그리고 합집합 max를 구하기 위해 min을 빼준다. 만일 max가 0이라면(전체 원소의 개수가 교집합과 같으면)? 65536을 리턴해야 한다. 이거 빼면 해당 조건에 걸릴 경우 나누기를 못한다. 무조건 해줘야 한다.

그리고 double형을 이용해 min과 max를 나누면 된다. double형을 이용하는 이유는 소수점까지 필요하기 때문이다.

마지막으로 구한 값에 65536을 곱하고 return하면 끝! 이때는 따로 형변환을 할 필요가 없다. 소수점은 떼고 구하라고 했기 때문에 int형은 자동으로 소수점을 뗀다는 점을 이용하자.

코드

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int solution(string str1, string str2) {
    int answer = 0;
    vector<string> str1_v;
    vector<string> str2_v;
    int max = 0;
    int min = 0;
    
    transform(str1.begin(), str1.end(), str1.begin(), ::tolower);
    transform(str2.begin(), str2.end(), str2.begin(), ::tolower);
    
    for(int i= 0; i<str1.length(); i++){
        string tmp = str1.substr(i, 2);
        if((tmp[0] >= 97 && tmp[0] <= 122) && (tmp[1] >= 97 && tmp[1] <= 122)){
            str1_v.push_back(tmp);
        }
    }
    
    for(int i= 0; i<str2.length(); i++){
        string tmp = str2.substr(i, 2);
        if((tmp[0] >= 97 && tmp[0] <= 122) && (tmp[1] >= 97 && tmp[1] <= 122)){
            str2_v.push_back(tmp);
        }
    }
    
    max = str1_v.size() + str2_v.size();
    
    if(str1.empty() && str2.empty()){
        return 65536;
    }
    
    if(str1_v.size() >= str2_v.size()){
        for(int i=0; i<str2_v.size(); i++){
            auto tmp = find(str1_v.begin(), str1_v.end(), str2_v[i]);
            cout << *tmp << " " << &tmp << endl;
            if(tmp != str1_v.end()){
                min++;
                str1_v.erase(tmp);
            }
        }
    }else{
        for(int i=0; i<str1_v.size(); i++){
            auto tmp = find(str2_v.begin(), str2_v.end(), str1_v[i]);
            if(tmp != str2_v.end()){
                min++;
                str2_v.erase(tmp);
            }
        }
    }
    
    max = max - min;
    
    if(max == 0){
        return 65536;
    }
    double j = (double)min/(double)max;
    answer = j * 65536;
    
    return answer;
}