[1차] 뉴스 클러스터링

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

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

몇가지 단계에 나누어서 처리하면 된다.

1. 2단어씩 자른다

2. 잘린 단어가 쓸 수 있는 단어인지 확인한다

3. 교집합 갯수를 구한다

4. 전체 총 갯수를 구한다.

5. 전체 총 갯수에서 교집합 수를 빼서 다시 전체 총 갯수를 만든다.

- 1,1,1,1,1 과 1,1,1 이 있을 경우 교집합은 3, 합집합은 5이다. 전체 총수 8 - 교집합수 = 총 갯수가 된다.

6. 교집합/총갯수 * 65536

- 주의 해야 할것은 모수가 되는 총 갯수가 0이면 무조건 1 return 이다.

- 그러나 여기서 1은 그냥 1이 아닌 * 65536이 곱해져야지만 답으로 인정된다.

 

//자카드 유사도 
//|-두 집합 A, B 사이의 자카드 유사도 J(A, B)는 두 집합의 교집합 크기 - 두 집합의 합집합 크기
//|-교집합 크기 - 합집합 크기
//|-예) A = {1, 2, 3}, 집합 B = {2, 3, 4} A ∩ B = {2, 3} A ∪ B = {1, 2, 3, 4} J(A, B) = 2/4 = 0.5
//|-집합 B 가 0 이면 = return 1

//문자열 FRANCE와 FRENCH  {FR, RA, AN, NC, CE}, {FR, RE, EN, NC, CH} 교집합은 {FR, NC}, 합집합은 {FR, RA, AN, NC, CE, RE, EN, CH}가 
//J("FRANCE", "FRENCH") = 2/8 = 0.25

//두 글자씩 끊어서 다중집합의 원소
//공백이나 숫자, 특수 문자가 들어있는 경우는 그 글자 쌍을 버린다
// 대문자와 소문자의 차이는 무시

//output = Math.floor(2/8 * 65536)
function solution(str1, str2) {
    let gr1 = new Map();
    let gr2 = new Map();
    str1 = str1.toLowerCase();
    str2 = str2.toLowerCase();
    
    let intersection = 0;
    let union = 0;
    
    for(let i = 0; i < Math.max(str1.length-1, str2.length-1); i++){
        if(i < str1.length-1){
            let word = str1.charAt(i) + str1.charAt(i+1);
            if(checkValidate(word)) gr1.set(word, ~~gr1.get(word)+1);
        }
        if(i < str2.length-1){
            let word = str2.charAt(i) + str2.charAt(i+1);
            if(checkValidate(word)) gr2.set(word, ~~gr2.get(word)+1);
        }
    }
    
    for(let [key,value] of gr1.entries()){
        if(gr2.has(key)){
            intersection += Math.min(gr1.get(key), gr2.get(key));
        }
    }
    for(let value of gr1.values()) union+=value;
    for(let value of gr2.values()) union+=value;
    
    union -= intersection;
    
    return union == 0 ? 1 * 65536 : Math.floor((intersection / union) * 65536);
    
    function checkValidate(word){
        
        for(let i = 0; i < 2; i++){
            if(!(word.charCodeAt(i) <= 'z'.charCodeAt(0) && 'a'.charCodeAt(0) <= word.charCodeAt(i))) return false;
        }
        return true;
    }
}