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

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

프로그래머스

 

접근법

- 우선 소문자와 대문자를 구분하지 않으므로 모두 소문자 혹은 대문자로 바꿔줘야한다.

그리고 합집합과 교집합을 구하면되는 간단한 문제인데 은근히 조건에 맞는 문자열을 구성하는 구현 실력을 요구했고 기본적인 집합 공식인 

A + B - A n B = A U B 

를 알고있어야했다.  

 

처음 접근했을 땐 set 자료구조에 모두 박아놓으면 합집합이 될 것이라 생각했으나 

 

1 2 2 3

2 2 3

 

이라하면 합집합은 2 2 3 인데 set에 넣으면 2 3만 들어가서 이건 틀린 접근이었다. 그래서 교집합을 먼저 구하는 것이 낫다. 교집합을 구할 때는 

 

1 2 2 3

2 2 3

 

에서 1은 없으므로 넘어가고

2는 2가 하나 있으므로 교집합 개수 + 1을 한 후 두 문자열에서 2를 제거해준다. 

그렇다면

 

1 2 3

2 3 

 

이된다. 그런데 i번째 였던 2가 제거되었기 때문에 지금 3을 바라보게 된다. 그러므로 i를 - 1 해준다.

 

int intersection = 0;
    for(int i = 0; i < vec1.size(); i++){
        for(int j = 0; j < vec2.size(); j++){
            if(vec1[i] == vec2[j]){
                intersection++;
                vec1.erase(vec1.begin() + i);
                vec2.erase(vec2.begin() + j);
                i--;
            }
        }
    }

 

코드로 보면 다음과 같다. vec1을 기준으로 확인하다가 같은것이 나오면 양쪽에서 모두 제거하고 i는 이번에 보던 것이 없어졌으므로 - 1 해주는 것이다. 

 

그리고 합집합은 미리 A의 크기 + B의 크기로 설정해두고 이후 집합 공식에 따라 intersection만큼 빼주면 된다. 

 

#include <string>
#include <set>
#include <iostream>
#include <vector>
using namespace std;

set<string> Union;

vector<string> vec1;
vector<string> vec2;

int solution(string str1, string str2) {
    double answer = 0;

    for(int i = 0; i < str1.size(); i++){
        str1[i] = toupper(str1[i]);
    }
    for(int i = 0; i < str2.size(); i++){
        str2[i] = toupper(str2[i]);
    }
    
    for (int i = 1; i < str1.size(); i++){
        string tmp = "";        
        tmp.push_back(str1[i - 1]);
        tmp.push_back(str1[i]);
        
        bool flag = true;
        
        for(int j = 0; j < 2; j++){
            if(tmp[j] <= 90 && tmp[j] >= 65) continue;
            flag = false;
        }
        if(flag)
            vec1.push_back(tmp);
    }
    
    for (int i = 1; i < str2.size(); i++){
        string tmp = "";        
        tmp.push_back(str2[i - 1]);
        tmp.push_back(str2[i]);
        
        bool flag = true;
        
        for(int j = 0; j < 2; j++){
            if(tmp[j] <= 90 && tmp[j] >= 65) continue;
            flag = false;
        }
        if(flag)
            vec2.push_back(tmp);
    }
    int unions = vec1.size() + vec2.size();
    int intersection = 0;
    for(int i = 0; i < vec1.size(); i++){
        for(int j = 0; j < vec2.size(); j++){
            if(vec1[i] == vec2[j]){
                intersection++;
                vec1.erase(vec1.begin() + i);
                vec2.erase(vec2.begin() + j);
                i--;
            }
        }
    }
    
    if(unions == 0) return 65536;
    
    unions -= intersection;
    answer = 1.0 * intersection / unions;
    answer *= 65536;
    return (int)answer;
}