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

 

 

 

 

 

풀이

---

 

내가 한 풀이는 좋은 풀이는 아닌 것 같다. 두 글자씩 나눠서 입력하는 부분을 함수로 만들어 코드 길이를 줄일 수 있었을 것이다. v1, v2에 각각 두 글자씩 묶은 문자열을 넣어준다. 이 때, 알파벳으로만 이루어져 있는 지 체크하고, 동시에 대문자는 소문자로 변경한다. 이는 대소문자 구분 없이 하기 위해서 이다.

 

교집합의 개수만 구했다. 교집합의 원소 개수를 알면, 합집합 원소 개수도 구할 수 있기 때문이다. A U B = A + B - A n B 공식을 이용한다.

 

중요한 점은 double을 이용해 형변한을 해서 소수점까지 나오게 한 뒤 계산해야 한다.

 

 

 

#include <string>
#include <vector>
#include <iostream>
#include <cmath>

using namespace std;

int solution(string str1, string str2) {
    int answer = 0;
    int n = 0;
    int n1, n2;
    vector<string> v1;
    vector<string> v2;
    
    for(int i = 0 ; i < str1.size() - 1; i++){
        string str = str1.substr(i, 2);
        str[0] = tolower(str[0]);
        str[1] = tolower(str[1]);
       
        if((str[0] <= 'z' && str[0] >= 'a' ) && (str[1] <= 'z' && str[1] >= 'a'))
            v1.push_back(str);
        
    }   
    
    for(int i = 0 ; i < str2.size() - 1; i++){
        string str = str2.substr(i, 2);
        str[0] = tolower(str[0]);
        str[1] = tolower(str[1]);
        if((str[0] <= 'z' && str[0] >= 'a' ) && (str[1] <= 'z' && str[1] >= 'a'))
            v2.push_back(str);
        
    }  
    
    n1 = v1.size();
    n2 = v2.size();

    if(n1 == 0 && n2 == 0) return 65536;
    
    for(int i = 0 ; i < v1.size();i++){
        for(int j = 0 ; j < v2.size(); j++){
            if(v1[i] == v2[j]){
                v2.erase(v2.begin() + j);
                n++;
                break;
            }
        }
    }
    
    double jaca = double(n) / double(n1 + n2 - n);
    
    answer = jaca * 65536;
    return answer;
}

 

 

 

다른 풀이

 

다른 풀이는 놀라웠는데, 두 알파벳을 조합하니 그 경우의 수는 26 * 26 = 676개가 나온다. 이 676개만큼 공간을 갖는 배열을 선언해서 푼 풀이를 봤다. 또한 헤더 ctype에 존재하는 isalpha라는 함수를 알게되었다.

 

#include <string>
#include <algorithm>
#include <unordered_map>

using namespace std;

int solution(string str1, string str2) {
    unordered_map<string, int> hash1;
    unordered_map<string, int> hash2;

    transform(str1.begin(), str1.end(), str1.begin(), ::tolower);
    transform(str2.begin(), str2.end(), str2.begin(), ::tolower); 

    for (int i = 0; i < str1.size() - 1; i++)
        if (isalpha(str1[i]) && isalpha(str1[i+1]))
            hash1[str1.substr(i, 2)]++;

    for (int i = 0; i < str2.size() - 1; i++)
        if (isalpha(str2[i]) && isalpha(str2[i+1]))
            hash2[str2.substr(i, 2)]++;  

    int intersection_count = 0;
    int union_count = 0;

    for (auto & p : hash1)
        intersection_count += min(p.second, hash2[p.first]);
    
    for (auto & p : hash1)
        union_count += p.second;

    for (auto & p : hash2)
        union_count += p.second;

    union_count -= intersection_count;

//    for (auto & p : hash1)
//        hash2[p.first] = max(hash2[p.first], p.second);

//    for (auto & p : hash2)
//        union_count += p.second;
    
    if (union_count == 0 && intersection_count == 0)
        return 65536;
    else
        return (double)intersection_count / union_count * 65536;
}

 

isalpha는 int isalpha (int c); 원형을 갖는다.

‘a’를 넣으면 자동으로 형변환이 일어나 아스키 코드 값이 들어간다.

 

A-Z 대문자면 1, 소문자면 2, 둘 다 아니면 0을 반환한다.

이 사람은 map을 사용한 모습이다. 똑같은 문자열이 있으면 개수를 늘린다.

 

두 문자열에서 교집합 원소가 발견되면, 그 둘중 작은 개수가 교집합 개수가 되고 그걸 추가해준다.

 

ex ) str1에 1이 2개, str2에 1이 3개면 교집합에 추가할 개수는 2

 

 

그 다음 합집합 개수를 구한다. 공식을 적용하거나, 주석처리한 부분처럼 최대값으로 second를 다 변환한 뒤 다 더해주는 방식을 사용한다.