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

문제설명

 

입력 형식

• 입력으로는 str1과 str2의 두 문자열이 들어온다. 각 문자열의 길이는 2 이상, 1,000 이하이다.
• 입력으로 들어온 문자열은 두 글자씩 끊어서 다중집합의 원소로 만든다. 이때 영문자로 된 글자 쌍만 유효하고, 기타 공백이나 숫자, 특수 문자가 들어있는 경우는 그 글자 쌍을 버린다. 예를 들어 "ab+"가 입력으로 들어오면, "ab"만 다중집합의 원소로 삼고, "b+"는 버린다.
• 다중집합 원소 사이를 비교할 때, 대문자와 소문자의 차이는 무시한다. "AB"와 "Ab", "ab"는 같은 원소로 취급한다.

출력 형식

입력으로 들어온 두 문자열의 자카드 유사도를 출력한다. 유사도 값은 0에서 1 사이의 실수이므로, 이를 다루기 쉽도록 65536을 곱한 후에 소수점 아래를 버리고 정수부만 출력한다.

예제 입출력

str1str2answer

FRANCE	french	16384
handshake	shake hands	65536
aa1+aa2	AAAA12	43690
E=M*C^2	e=m*c^2	65536

 

 

=> MAP 자료형과 SET자료형을 사용하여 풀이를 하였습니다. 

• 주어진 문자열을 대문자화 시킵니다. 
• MAP자료형을 활용하여 map1 과 map2를 생성합니다. ( 각 문자열의 원소집합 => key , 원소집합이 나타난 수 => value) 
• SET자료형을 활용하여 두 문자열에 나타난 모든 원소의 집합을 나타냅니다. 
• 교집합 : min ( map1[] , map2[] ) 
• 합집합 : max( map1[], map2[] ) 
• 위와 같이 표현합니다. 

=> 기본알고리즘의 구성은 위와 같습니다. 자세한 풀이는 아래의 사진을 참조해주시기 바랍니다. 

 

문제풀이 

#include <string>
#include <algorithm> 
#include <set>
#include <map>
#include <iostream>

#define mulNum 65536    

using namespace std;;

int solution(string str1, string str2) {
    int answer = 0;
    
    map<string,int> map1,map2; //각 str 다중집합 map
    set<string> allStr; // 전체 다중집합 set
    
    //소문자 => 대문자화 
    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]);
    }
    
    
    //map과 set채워넣기
    string tmp;
    for(int i=0; i< str1.size()-1; i++)
    {
        if((str1[i] >= 'A' && str1[i]<='Z') && (str1[i+1] >= 'A' && str1[i+1]<='Z')) // 문자라면
        {
            tmp =str1.substr(i,2);
            map1[tmp]++;
            allStr.insert(tmp);
        }
    }
     for(int i=0; i< str2.size()-1; i++)
    {
        if(str2[i] >= 'A' && str2[i]<='Z' && str2[i+1] >= 'A' && str2[i+1]<='Z') // 문자라면
        {
            tmp =str2.substr(i,2);
            map2[tmp]++;
           // cout << tmp<<" ";
            allStr.insert(tmp);
        }
    }
    
    
    for(auto k : allStr)cout << k<<" ";
    
    //자키드유사도추출
    //교집합과 합집합의 크기 구하기 
    int inter=0;
    int uni=0; 
    
    for(auto i : allStr)
    {
        inter += min(map1[i], map2[i]);
        uni += max(map1[i], map2[i]);
        cout << i <<'\n';
        cout << map1[i] <<" "<<map2[i]<<'\n';
    }
    
    if(inter ==0 && uni ==0) return mulNum;
    
    answer = mulNum*inter / uni;
    
    return answer;
}