[프로그래머스/C++] 뉴스 클러스터링

1.문제 링크

뉴스 클러스터링

2. 풀이 전 계획과 생각

• 집합 자료구조 이용

3. 풀이

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

int solution(string str1, string str2) {
    set<string> s1, s2;
    vector<string> v1, v2;
    for(int i=0; i<str1.size()-1;i++){
        string temp = str1.substr(i,2);
        int c1 = int(temp[0]);
        int c2 = int(temp[1]);
        if(65<=c1&&c1<=90 || 97<=c1&&c1<=122){
            if(97<=c1&&c1<=122) temp[0]-=32;
        }
        else continue;
        if(65<=c2&&c2<=90 || 97<=c2&&c2<=122){
            if(97<=c2&&c2<=122) temp[1]-=32;
        }
        else continue;

        s1.insert(temp);
        v1.push_back(temp);
    }

    for(int i=0; i<str2.size()-1;i++){
        string temp = str2.substr(i,2);
        int c1 = int(temp[0]);
        int c2 = int(temp[1]);
        if(65<=c1&&c1<=90 || 97<=c1&&c1<=122){
            if(97<=c1&&c1<=122) temp[0]-=32;
        }
        else continue;
        if(65<=c2&&c2<=90 || 97<=c2&&c2<=122){
            if(97<=c2&&c2<=122) temp[1]-=32;
        }
        else continue;

        s2.insert(temp);
        v2.push_back(temp);
    }

   
    if(s1.size()==0 && s2.size()==0){
        return 65536;
    }

    vector<string> buffer_union(s1.size()+s2.size());
    auto iter = set_union(s1.begin(), s1.end(), s2.begin(), s2.end(), buffer_union.begin());
    buffer_union.erase(iter, buffer_union.end());

    vector<string> buffer_intersect(s1.size()+s2.size());
    iter = set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), buffer_intersect.begin());
    buffer_intersect.erase(iter, buffer_intersect.end());

    int buffer_union_size = buffer_union.size();
    int buffer_intersect_size = buffer_intersect.size();

    for(int i=0;i<buffer_union.size();i++){
        int cnt = max(count(v1.begin(),v1.end(),buffer_union[i]),
                      count(v2.begin(),v2.end(),buffer_union[i]));
        if(cnt!=1){
            buffer_union_size+=(cnt-1);
        }
    }
    for(int i=0;i<buffer_intersect.size();i++){
        int cnt = min(count(v1.begin(),v1.end(),buffer_intersect[i]),
                      count(v2.begin(),v2.end(),buffer_intersect[i]));
        if(cnt!=1){
            buffer_intersect_size+=(cnt-1);
        }
    }

    double temp = (double)buffer_intersect_size/buffer_union_size;
   
    double answer = floor(temp*65536);

    return answer;
}

1. 입력으로 주어진 str1, str2에 대해 2개씩 잘라 영문자로만 이루어진 것만 모두 대문자로 만들어 set 자료형과 vector 자료형에 입력으로 넣는다.

2. 1번 결과로 str1문자열 데이터는 s1, v1이 생기고, str2문자열 데이터는 s2, v2가 생기게 된다.

3. 만약 s1과 s2 크기가 모두 0이라면 65536을 반환.

4. s1과 s2 집합 자료형에 대해서 합집합과 교집합을 수행해 그 결과의 크기를 저장한다.

5. v1과 v2 벡터 자료형에 대해서 4번에서 만든 교집합에 대해서는 벡터에 더 적은 개수를 가지고 있는 개수 수를 1을 빼서 더하고, 합집합에 대해서는 벡터에 더 많은 개수를 가지고 있는 개수 수를 1을 빼서 더한다.

6. 문제 조건에 주어진대로 계산한다.

4. 풀이하면서 고민했던 점

• 다중집합에서 어떻게 합집합과 교집합을 구할지 고민함. 벡터 자료형을 만들어 구현함.

5. 문제를 풀고 알게된 개념 및 소감

• 집합 자료형 사용법과 교집합, 합집합 계산 방법을 알게됨.

• 정수끼리의 나눗셈에서 소숫점을 얻기 위해서는 둘 중 한개 이상을 double형으로 만들어야 한다.