알고리즘(C++) / 프로그래머스 level 2 : 뉴스 클러스터링

level 2 : 뉴스 클러스터링

https://programmers.co.kr/learn/courses/30/lessons/17677?language=cpp 

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

 

코드

//프로그래머스 뉴스 클러스터링
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(string str1, string str2) {
    int answer = 0;
    vector <string> s1;
    vector <string> s2;

    //str1 집합
    for (int i = 0; i < str1.size() - 1; i++) {
        string s = "";

        //알파벳이 아닐때
        if (!isalpha(str1[i]) || !isalpha(str1[i+1]))
            continue;

        //대문자로 변환
        s += toupper(str1[i]);
        s += toupper(str1[i+1]);
        s1.push_back(s);
    }
    //str2 집합
    for (int i = 0; i < str2.size() - 1; i++) {
        string s = "";

        //알파벳이 아닐때
        if (!isalpha(str2[i]) || !isalpha(str2[i + 1]))
            continue;

        //대문자로 변환
        s += toupper(str2[i]);
        s += toupper(str2[i + 1]);
        s2.push_back(s);
    }


    int sum = s1.size() + s2.size();
    int common = 0;

    if (sum == 0)
        return 65536;

    for (int i = 0; i < s1.size(); i++) {
        auto it = find(s2.begin(), s2.end(), s1[i]);
        //교집합이 있을 때
        if (it != s2.end()) {
            s2.erase(it);
            common++;
        }
    }
    
    answer = (common * 65536) / (sum - common);
    return answer;
}

int main() {
    string str1 = "aa1+aa2";
    string str2 = "AAAA12";

    cout << solution(str1, str2) << "\n";

    return 0;
}

 

설명

vector s1, s2를 만들어 각 A와 B의 집합을 만들어 넣어주었다. 여기서 알파벳 이외의 문자가 포함되면 안 되므로 isalpha() 함수를 사용하여 이 문자가 알파벳인지 아닌지 확인해서 집합을 만들어 줄 수 있다. 

이때 s1, s2 벡터의 사이즈가 모두 0이면 65536을 바로 return 해준다. 

이후 find()함수를 사용하여 교집합이 있는 문자를 찾아주어 common을 증가시켜준다.

합집합은 벡터 s1과 s2를 더하여 교집합을 뺀 값이다. 

유사도에 65536을 곱하여 return 해준다. 

 

고찰

toupper('a') // 대문자 변환
tolower('A') // 소문자 변환

다음 함수는 각각 대문자 변환, 소문자 변환을 해준다. 두 함수는 문자를 쉽게 대소문자로 변환해준다. 이때 주의할 점은 두 함수 반환형은 int형이라는 것이다. 이 부분만 조심해서 문자를 변환할 수 있다. 

 

isalpha('a') // 알파벳 확인 

isalpha() 함수는 문자가 알파벳인지 아닌지 확인해준다.

이 함수를 사용하여 알파벳인지 아닌지 쉽게 확인이 가능하다.