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

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

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

<풀이>

1. 주어진 두 개의 문자열을 두 글자씩 끊어서 다중집합으로 만듭니다.

2. 두 집합의 교집합, 합집합 원소의 개수를 구한 후 자카드 유사도를 계산합니다.

3. 자카드 유사도를 반환합니다.

 

<해법>

1. 두 개의 다중집합의 교집합 원소 개수를 구하는 방법

=> 저는 아래 그림과 같은 방법으로 진행하였습니다. 모든 원소를 비교하면서, 비교해서 같은 원소는 다시 비교되지 않도록 맵핑을 하였습니다.

 

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
 
using namespace std;
 
//문자 판단 함수
bool isChar(char c) {
    if (c >= 'a' && c <= 'z') {
        return true;
    }
    return false;
}
 
int solution(string str1, string str2) {
    int answer = 0;
 
    //2글자씩 끊어서 저장할 벡터
    vector<string> v1, v2;
 
    //교집합 개수, 합집합 개수 변수
    int bunja = 0;
    int bunmo = 0;
 
    //대문자 -> 소문자 변환
    for (int i = 0; i < str1.length(); i++) {
        str1[i] = tolower(str1[i]);
    }
    for (int i = 0; i < str2.length(); i++) {
        str2[i] = tolower(str2[i]);
    }
 
    //문자열에서 문자만 2글자씩 잘라 벡터에 저장
    for (int i = 0; i < str1.length() - 1; i++) {
        if(isChar(str1[i]) && isChar(str1[i + 1])) {
            v1.push_back(str1.substr(i, 2));
        }
    }
    for (int i = 0; i < str2.length() - 1; i++) {
        if (isChar(str2[i]) && isChar(str2[i + 1])) {
            v2.push_back(str2.substr(i, 2));
        }
    }
 
    //교집합 개수 찾기
    for (int i = 0; i < v1.size(); i++) {
        for (int j = 0; j < v2.size(); j++) {
            
            //같은 원소가 있다면, 교집합 개수 + 1
            if (v1[i] == v2[j]) {
 
                bunja++;
                
                //해당 원소를 다시 셀 수 없도록 맵핑
                v2[j] = "#";
 
                break;
            }
        }
    }
 
    //결과 계산
    bunmo = v1.size() + v2.size() - bunja;
 
    if (bunmo == 0) {
        answer = 65536;
    }
    else {
        answer = bunja * 65536 / bunmo;
    }
 
    //결과 반환
    return answer;
}

 

구현에 대해 알아볼 수 있는 문제였습니다.