[ 프로그래머스 / 문자열 ] 뉴스 클러스터링 (KaKao)

1. 문제

---

 

코딩테스트 연습 - [1차] 뉴스 클러스터링

 

 

2. 소스코드

---

- unordered_map을 이용해서 직관적으로 구현했다. 공식 해설에선 이 방법을 사용하지 않더라.

- 문자열을 쪼개서 각각 map에 저장한다. 중복되는 문자열이 발생할때마다 value값을 ++해서 몇 개인지 파악.

- 두 맵을 순회하면서 교집합 크기와, 총 합집합 크기를 카운트한다.

- 정말 간단한데, 합집합 크기를 계속 잘못 구해서 시간이 오래걸렸다.

 

소스코드

#include <string>
#include <iostream>
#include <unordered_map>
#define BASE 65536
using namespace std;

void splitString(string str, unordered_map <string, int>& map) {
    int len = str.length();
    for (int i = 0; i < len - 1; ++i) {
        string temp = str.substr(i, 2);
        bool isValid = true;
        for (int j = 0; j < 2; ++j) {
            temp[j] = tolower(temp[j]);
            if (!((int)temp[j] >= 97 and (int)temp[j] <= 122))
                isValid = false;
        }
        if (isValid) map[temp]++;
    }
    return;
}

int solution(string str1, string str2) {
    unordered_map <string, int> A, B;
    splitString(str1, A);
    splitString(str2, B);

    int com = 0, sum = 0;

    for (auto idx = A.begin(); idx != A.end(); ++idx)
        if (B.find(idx->first) == B.end()) {
            sum += idx->second;
        }
    for (auto idx = B.begin(); idx != B.end(); ++idx) {
        if (A.find(idx->first) == A.end()) {
            sum += idx->second;
        }
        else {
            com += min(A.find(idx->first)->second, idx->second);
            sum += max(A.find(idx->first)->second, idx->second);
        }
    }
    
    if (sum == 0) return 1 * BASE;
    return (int)((double)com / sum * BASE);
}