Programmers : 뉴스 클러스터링

풀이 요약

맵,셋

풀이 상세

1. 문제에서 중요한 점은 다음과 같다.

   • 두문자를 이용해 집합을 구할 때, 합집합과 교집합을 구하는 방법에 대해 생각할 필요가 있다.
   • 필터링 과정이 필요하다. 대문자 소문자를 구분없이 진행하며, 영어가 아닌 구성은 제외해야 한다.

2. 먼저 map 을 활용해 주어진 문자열의 두 문자 구성에 대한 맵을 구한다. 나의 중복을 포함한 모든 경우의 수를 구하기 위해, 해당 구성에 대한 갯수를 반환하는 함수를 만들었다.

3. 두 map 을 이용해 교집합을 구한다. 만약 임의의 두문자 구성에 대한 두 문자열이 가진 맵의 최솟값이 교집합이 된다. {FR, RA, AN, NC, CE}, {FR, RE, EN, NC, CH} 의 경우, 총 2의 교집합이 나타난다. 해당하지 못하는 차집합들은 모두 상대방 map 에서 0을 반환할테니 교집합에 적용되지 않는다.

4. 합집합은 모든 경우의 수 - 교집합 이 합집합이 된다.

5. 만약 교집합 합집합이 0이면 65536 을 해당 조건에 포함되지 않는 경우는 문제가 원하는 풀이대로 반환하면 된다.

배운점

• c++ 은 toLowercase() 함수가 없어서 찾아보니, transform 함수를 적용하여 마치 forEach 와 같은 함수 효과를 낼 수 있다. tolower() 함수는 char 한개의 문자를 소문자로 바꾸는데 해당 함수를 transform 의 4번째 매개변수로 넣는 경우, 모든 항목에 대해 매개변수를 대입한 결과 값으로 변화시킨다. 만약 숫자 vector 를 사용하는 경우에는 4번째 매개변수에 *2 를 반환하는 것을 통해 모든 인덱스 값이 2배 늘어나게 할 수도 있는 것이다.

#include <string>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
using namespace std;
unordered_map<string, int> m1, m2;
unordered_set<string> ss;
// m1 요소의 총 경우의 수, m2 요소의 총 경우의 수, cross cnt: 교집합 수, union cnt: 합집합 수
int len1, len2, cc, unc; 
int make_map(unordered_map<string, int> &m, string &s) {
    transform(s.begin(), s.end(), s.begin(), ::tolower);
    string temp;
    int cnt = 0;
    for(int i=0; i<s.size()-1; i++) {
        temp = "";
        if(s[i]>='a' && s[i]<='z' && s[i+1] >= 'a' && s[i]<='z') {
            temp+=s[i], temp+=s[i+1];
            m[temp]++;
            ss.insert(temp);
            cnt++;
        }
    }
    return cnt;
}

void crossCnt()  {
    for(auto str : ss) {
        cc += min(m1[str], m2[str]);
    }
}

int solution(string str1, string str2) {
    // 두 언어를 이용한 맵 만들기
    len1 = make_map(m1, str1);
    len2 = make_map(m2, str2);
    int total = len1+len2;
    // 두 언어를 이용한 교집합 갯수 구하기
    crossCnt();
    // 합집합 구하기 
    unc = total - cc;
    if(!cc && !unc) return 65536;
    return (double) cc / (double) unc * 65536;
}