[C++] level2 뉴스 클러스터링 17677

📌뉴스 클러스터링

/* 문제 설명은 링크로 대체 */

📌풀이

먼저 문제에 몇가지 조건이 있다.

1. 입력으로 들어온 문자열은 두 글자씩 끊어서 다중집합의 원소로 만든다.
2. 자카드 유사도 방법을 이용한다.
3. "AB"와 "Ab", "ab"는 같은 원소로 취급 (대소문자 구분 X)
4. 원소의 중복을 허용하는 다중집합에 대해서 확장할 수 있다.
   ex. 다중집합 A = {1, 1, 2, 2, 3}, 다중집합 B = {1, 2, 2, 4, 5}라고 하면, *교집합 A ∩ B = {1, 2, 2}, 합집합 A ∪ B = {1, 1, 2, 2, 3, 4, 5} *

이를 바탕으로 다음과 같이 문제에 접근하였다.
자카드 유사도( J(a, b) = a, b의 교집합개수 / a,b의 합집합개수 )이라고 문제에 방법이 명시되어 있다.

집합 a와 b를 생성하였고, str1, str2를 모두 소문자로 변환한 뒤 split()함수를 구현하여 두글자씩 잘라 !문자!만 넣어주었다.

교집합의 개수와 합집합의 개수를 구해야 자카드 유사도를 구할 수 있다!

교집합의 개수는 2가지로 나눠서 구하였다.

1. a집합을 돌면서 b집합에서 a원소와 동일한 값이 존재할 때 교집합으로 하고, a집합에서 동일 값을 지웠다.
2. b집합에 대해서도 1과 동일한 방법으로 진행한다.

-> 이렇게 하면 두 집합을 각각 돌면서 교집합을 구할 수 있따.

합집합의 개수는 교집합의 개수와 원래 a집합과 b집합의 크기로 구할 수 있다. (수학공식 이용)

주의 할 점

1. 교집합을 구하면서 동일 값을 지우기 때문에 a집합과 b집합의 크기 합은 미리 교집합 탐색 전에 진행해야 한다.
2. 문제에서 각 집합이 공집합인 경우 return 해야 한다고 명시되어 있으므로 &&연산을 이용한다. //안하면 testcase 5에서 오류남

   if(a.empty() && b.empty()) return 65536;

📌코드

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

void split(string str, vector<string>& v){
    for(int i = 0; i < str.size() - 1; i++){
        string temp = str.substr(i, 2); //2개씩 잘라
        //두 글자가 모두 문자인 경우에만 v에 추가
        if(temp[0] >= 'a' && temp[0] <= 'z' && temp[1] >= 'a' && temp[1] <= 'z') 
            v.push_back(temp);
    }
}

int solution(string str1, string str2) {
    int gyo = 0, hab = 0;
    double jacade = 0; //J(A, B)는 소수 값

    //집합 a, b //2글자씩 잘라서 보관
    vector<string> a;
    vector<string> b;

    //str1과 str2를 모두 소문자로 변환
    transform(str1.begin(), str1.end(), str1.begin(), ::tolower);
    transform(str2.begin(), str2.end(), str2.begin(), ::tolower);

    split(str1, a); // str1 2개씩 잘라 집합 a 생성
    split(str2, b); // str2 2개씩 잘라 집합 b 생성

    //2개 집합 모두 빈 값 비교할 게 없으므로 -> 65536 return //testcase5 
    if(a.empty() && b.empty()) return 65536;


    //두 집합의 개수를 더한다. (교집합을 찾은 경우, 집합에서 지울 것이기 때문에)
    hab = a.size() + b.size();

    //배열을 탐색하며 교집합의 개수을 구한다.
    if(a.size() > b.size()){
        for(auto iter : b){
            auto find_str = find(a.begin(), a.end(), iter); //a집합에서 iter와 같은 문자열을 반환
            if(find_str != a.end()){ //b집합에서 찾았다면
                gyo++;
                a.erase(find_str);
            }
        }    
    }else{
        for(auto iter : a){
            auto find_str = find(b.begin(), b.end(), iter); //b집합에서 iter와 같은 문자열을 반환
            if(find_str != b.end()){ //a집합에서 찾았다면
                gyo++;
                b.erase(find_str);
            }
        }
    }

    //합집합의 개수는 a.size() + b.size() - 교집합.size() 이므로
    hab -= gyo;

    if(hab == 0) return 65536; //합집합이 0이라면 나눌 수 없으므로
    else jacade = (double) gyo / (double) hab;

    return jacade * 65536;
}

회고

처음에 코테 문제 풀기 시작할 땐 그냥 보이는대로 닥치는대로 코딩하기 시작했는데 요즘은 어려운 문제들과 로직이 필요한 문제들을 만나면서 새로운 습관이 생겼다.

1. 연습장에 문제 예제를 정리해보면서 로직 찾기
2. 주석을 달아가면서 코딩하기
   확실히 이 2가지를 지키면서 코딩하니 전보다는 그래도 조금 더 나은 것 같다.

이 문제는 제법 재밌게 풀었던 ....

---