[C++] 프로그래머스 : [1차] 뉴스 클러스터링

https://programmers.co.kr/learn/courses/30/lessons/17677

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

---

 문제 풀이

문자열에 대한 이해가 필요한 문제이다.

저장할 2자리 문자열이 여러 개인지 체크를 하기 위해서 맵을 구현해 저장할 것이다.

두 맵에 모두 2자리 문자열이 없다면 벡터에 push 해준다. 

나중에 원소를 확인하기 편리하게 하기 위해 벡터에 중복이 없는 2자리 문자열들을 저장한다.

 느낀 점

처음에는 반대로 union된 집합을 맵으로 구현했고 벡터에 따로 2자리로 잘라둔 문자열들을 저장했다. 맵을 통해서 따질 때에는 시간 복잡도가  최소 O(n^2)이 돼서 엎어버렸다. 처음에 떠오른 아이디어가 틀렸음에도 그 아이디어를 버리는 것이 너무 어려웠다. 아직은 많이 부족한 것 같다.

 코드

#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <cctype>

using namespace std;

int solution(string str1, string str2) {
    int answer = 65536, inter, uni;
    inter = uni = 0;
    map<string, int> m1, m2;
    vector<string> v;

    for (int i = 0; i < str1.length() - 1;i++) {
        string tmp = "";
        if (isalpha(str1[i]) == 0 || isalpha(str1[i + 1]) == 0) continue;
        for (int j = 0; j < 2; j++) {
            tmp += toupper(str1[i + j]);
        }
        if (m1[tmp] == 0 && m2[tmp] == 0) v.push_back(tmp);
        m1[tmp]++;

    }

    for (int i = 0; i < str2.length() - 1;i++) {
        string tmp = "";
        if (isalpha(str2[i]) == 0 || isalpha(str2[i + 1]) == 0) continue;
        for (int j = 0; j < 2; j++) {
            tmp += toupper(str2[i + j]);
        }
        if (m1[tmp] == 0 && m2[tmp] == 0) v.push_back(tmp);
        m2[tmp]++;
    }

    if (v.empty()) return answer;

    for (int i = 0; i < v.size();i++) {
        inter += min(m1[v[i]], m2[v[i]]);
        uni += max(m1[v[i]], m2[v[i]]);
    }

    return answer * inter / uni;
}