[집합] 뉴스 클러스터링 - 2018 KAKAO BLIND RECRUITMENT

해결 방법

i) str1, str2에 있는 대문자를 모두 소문자로 전환한다.

ii) str1, str2에 대하여 각각 연속된 두 영문자씩 쪼개어 벡터에 넣어준다.

iii) 두 벡터의 크기가 모두 0인 경우와 두 벡터 중 하나의 크기가 0인 경우를 반영한다.

iv) 두 벡터의 교집합 요소를 찾는다. 값이 같은 요소가 있기 때문에 방문 배열을 활용한다.

v) 합집합 요소의 개수를 찾는다. 합집합 요소는 두 벡터의 크기의 합에서 교집합 요소의 개수를 뺀 값이다.

-> n(A∪B)=n(A)+n(B)-n(A∩B)

 

 

소스 코드

#include <string>
#include <vector>
using namespace std;
vector<string> s1;
vector<string> s2;
int inter; // 교집합 요소의 개수
bool check[1001]; //s2의 교집합 요소 체크
string tmp;

int solution(string str1, string str2) {
    for(int i=0;i<str1.length();i++) if(str1[i]>='A'&&str1[i]<='Z') str1[i]+=32;
    for(int i=0;i<str2.length();i++) if(str2[i]>='A'&&str2[i]<='Z') str2[i]+=32;
    for(int i=0;i<str1.length();i++){
        tmp=str1.substr(i, 2);
        if(tmp[0]>='a'&&tmp[0]<='z'&&tmp[1]>='a'&&tmp[1]<='z') s1.push_back(tmp);
    }
    for(int i=0;i<str2.length();i++){
        tmp=str2.substr(i, 2);
        if(tmp[0]>='a'&&tmp[0]<='z'&&tmp[1]>='a'&&tmp[1]<='z') s2.push_back(tmp);
    }
    if(s1.size()==0&&s2.size()==0) return 65536;
    if(s1.size()==0||s2.size()==0) return 0;
    for(int i=0;i<s1.size();i++){
        for(int j=0;j<s2.size();j++){
            if(s1[i]==s2[j]&&!check[j]){ // 교집합 부분인 s2 체크
                check[j]=true;
                inter++;
                break;
            }
        }
    }
    return inter*65536/(s1.size()+s2.size()-inter);
}

 

테스트케이스 13개 모두 정답