[프로그래머스] 2단계 - [1차] 뉴스 클러스터링

문제 설명

두 문장의 자카드 유사도 return

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

프로그래머스

 

 

문제 풀이법

처음에는 map으로 구현을 했다가 map의 키 값으로 합집합을 구하는 실수를 해버렸다

이후에는 map에 있는 값을 중복을 제거하면서 구현하려고 했으나 4, 5, 7, 9, 10, 11번 테케를 통과하지 못하였다

특히 str1 = "abc", str2 = "abbb" 인 경우를 해결하지 못하였다

위의 경우는 합집합이 { "ab, "bc", "bb", "bb" }이어야 하는데, 내가 구현한 코드는 str1에서 저장한 map의 값을 str2에서 빼주다 보니 { "ab", "bc", "bb" } 가 되어버렸다 - 7번 테케에서 실패하면 이 부분 참고해보세요

이 부분에 대해서 예외처리를 하다보니 너무 복잡해 져서 map으로 구현하는 것 대신 vector를 사용하였다

 

우선 str1, str2 각각 for문을 돌면서 해당 인덱스와 앞의 인덱스의 값이 알파벳인지 확인 후에 소문자로 변환해서 vector에 값을 넣었다

합집합을 계산하기 위해 str1과 str2 각각의 집합을 담은 vector 값의 size를 우선 더해준다 (이후에 교집합 뺌)

 

str2의 집합을 담은 vector<string> v2를 기준으로 v1에 값이 있는지 확인하고 값이 있으면 v1에 있는 값을 삭제한다

값이 있다면 교집합이므로 삭제하면서 교집합 cnt를 하나씩 더해준다

 

모든 처리를 끝내고 합집합이 0이면 공집합이므로 이때는 0으로 나눌 수는 없으니 교집합, 합집합 모두 1로 맞춰준다 - 5번, 13번 테케에서 틀리면 이 부분을 참고해보세요

(교집합이 0인 기준으로 설정했다가 틀림) 

 

이후 앞에서 계산한 합집합에서 교집합을 빼면 진정한 합집합을 계산할 수 있다

 

return은 double로 형변환 선언을 한 상태로 자카드 유사도를 계산해주었다 - 이 부분도 double 앞에 안붙이면 테케 틀릴 수 도 있습니다

 

 

처음에 합집합을 map의 key 개수로 구하는 바람에 시간을 너무 많이 버렸다

map 대신 vector를 쓴 선택은 좋았지만, 나중에 map으로도 푸는 방법을 알아봐야겠다 

 

 

소스 코드

#include <string>
#include <vector>
#include <cctype>
#include <cmath>

using namespace std;

int solution(string str1, string str2) {
    int answer = 0;
    
    int inter_cnt = 0;
    int union_cnt = 0;
    
    int str1_cnt = 0;
    int str2_cnt = 0;
    
    vector<string> v1;
    vector<string> v2;
    
    for (int i = 1; i < str1.size(); i++) {
        if (isalpha(str1[i - 1]) && isalpha(str1[i])) {
            string s = "";
            char c1 = tolower(str1[i - 1]);
            char c2 = tolower(str1[i]);
            s += c1;
            s += c2;
            
            v1.push_back(s);
        }
    }
    
    vector<string> v;
    for (int i = 1; i < str2.size(); i++) {
        if (isalpha(str2[i - 1]) && isalpha(str2[i])) {
            string s = "";
            char c1 = tolower(str2[i - 1]);
            char c2 = tolower(str2[i]);
            s += c1;
            s += c2;
            
            v2.push_back(s);
        }
    }
    
    union_cnt = v1.size() + v2.size();
        
    for (int i = 0; i < v2.size(); i++) {
        for (int j = 0; j < v1.size(); j++) {
            if (v2[i] == v1[j]) {
                v1.erase(v1.begin() + j);
                inter_cnt++;
                break;
            }
        }
    }
    
    //공집합일 경우
    if (union_cnt == 0) {
        inter_cnt = 1;
        union_cnt = 1;
    }
    else
        union_cnt -= inter_cnt;
    
    answer = ((double)inter_cnt / (double)union_cnt) * 65536;

    return answer;
}