[프로그래머스] 뉴스 클러스터링 (level2, c++)

 

문제

---

자카드 유사도는 집합 간의 유사도를 검사하는 여러 방법 중의 하나로 알려져 있다. 두 집합 A, B 사이의 자카드 유사도 J(A, B)는 두 집합의 교집합 크기를 두 집합의 합집합 크기로 나눈 값으로 정의된다.

문자열 "FRANCE"와 "FRENCH"가 주어졌을 때, 이를 두 글자씩 끊어서 다중집합을 만들 수 있다. 각각 {FR, RA, AN, NC, CE}, {FR, RE, EN, NC, CH}가 되며, 교집합은 {FR, NC}, 합집합은 {FR, RA, AN, NC, CE, RE, EN, CH}가 되므로, 두 문자열 사이의 자카드 유사도 J("FRANCE", "FRENCH") = 2/8 = 0.25가 된다.

입력으로 들어온 두 문자열의 자카드 유사도를 출력한다. 유사도 값은 0에서 1 사이의 실수이므로, 이를 다루기 쉽도록 65536을 곱한 후에 소수점 아래를 버리고 정수부만 출력한다.

문제조건

---

• 입력으로는 str1과 str2의 두 문자열이 들어온다. 각 문자열의 길이는 2 이상, 1,000 이하이다.
• 입력으로 들어온 문자열은 두 글자씩 끊어서 다중집합의 원소로 만든다. 이때 영문자로 된 글자 쌍만 유효하고, 기타 공백이나 숫자, 특수 문자가 들어있는 경우는 그 글자 쌍을 버린다. 예를 들어 "ab+"가 입력으로 들어오면, "ab"만 다중집합의 원소로 삼고, "b+"는 버린다.
• 다중집합 원소 사이를 비교할 때, 대문자와 소문자의 차이는 무시한다. "AB"와 "Ab", "ab"는 같은 원소로 취급한다.

풀이

---

 처음에 문제를 잘못 이해해서 시간을 많이 허비했다. 문제 조건에서 "ab+"가 입력으로 들어오면, "ab"만 다중집합의 원소로 삼고, "b+"는 버린다. 부분을 잘못 이해하고 문자열을 모두 소문자로 만들때 알파벳이 아닌 글자를 모두 삭제해주었다. 하지만 이렇게 하면 E=M*C^2의 경우에 결과가 {em, mc}가 나옴으로 옳지 않은 방법이다(공집합이 나와야 함). 그냥 직접 다 해보면서 알파벳인지 아닌지를 확인하여 다중 집합을 만들어주어야 한다.

 교집합은 사람이 교집합을 구하듯이 집합을 비교하며 같은 값이 나온다면 그 값은 집합에서 제외시키는 방법으로 구현해 주었다. 진짜로 빼주지는 않았고 대문자 X로 값을 바꿔 주어 중복 카운트가 안되도록 해 주었다. 합집합은 A집합의 크기+B집합의 크기 - 교집합의 크기를 사용하여 구해 주었다.

 다른분들 풀이처럼 투포인터 알고리즘을 사용하면 조금 더 짧게 문제를 풀 수 있는 것 같다.

코드

---

#include <string>
#include <vector>

using namespace std;

vector <string> oneString;
vector <string> twoString;

int DIV = 65536;

string lower(string str){
    string lowerStr = "";
     for(int i=0; i<str.length(); i++){
        char a = tolower(str[i]);
        lowerStr+=a;
    }
    return lowerStr;
}


int solution(string str1, string str2) {
    int answer = 0;
    
    //소문자로 변환
    string lower1 = lower(str1);
    string lower2 = lower(str2);
    
    //다중 집합 만들기
    string pair= "";
    for(int i=0; i<lower1.length()-1; i++){
        char a = lower1[i];
        char b = lower1[i+1];
        if(a>='a'&&a<='z'&&b>='a'&&b<='z'){
            pair+=a; pair+=b;
            oneString.push_back(pair);
            pair = "";
        }
    }
    
    for(int i=0; i<lower2.length()-1; i++){
        char a = lower2[i];
        char b = lower2[i+1];
        if(a>='a'&&a<='z'&&b>='a'&&b<='z'){
            pair+=a; pair+=b;
            twoString.push_back(pair);
            pair = "";
        }
    }
    
  	
    //교집합과 합집합이 모두 0이라면 -> 65536
    if(oneString.size()==0&&twoString.size()==0) return DIV;
    
    //교집합 구하기
    int strInter = 0;

    for(int i=0; i<oneString.size(); i++){
        for(int j=0;j<twoString.size(); j++){
            if(oneString[i]==twoString[j]) {
                strInter++;
                twoString[j]='X';
                break;
            }
        }
    }
    
    int strUnion = oneString.size()+twoString.size()-strInter;
    
    if(strInter==0) return 0;
    answer = strInter*DIV/strUnion;
   
    return answer;
}