[프로그래머스] 뉴스 클러스터링 (javascript)

주어진 두개의 문자열에 대해 자카드 유사도를 리턴하는 문제이다.

 

자카드 유사도란 문자열을 2개씩 나누어 쪼개고

france => fr, ra, an, nc, ce, french => fr, re, en, nc, ch

합집합과 교집합의 원소 갯수를 구해 나눈 것이다.

insersection => {fr, nc} union => {fr, ra, an, nc, ce, re, en, ch}

2/8 = 0.25

 

유의할 점이 있는데

1. 여기서 합집합과 교집합을 구할 때, 중복을 허용하는 집합이라는 점에 유의해야 한다.

예를들어 aaaa, aaa가 주어졌다면 => [aa, aa, aa] [aa, aa]

중복을 허용하지 않는다면 교집합은 [aa]가 되겠지만, 이 문제의 경우 중복을 허용하기 때문에 [aa, aa]가 된다. 따라서 교집합을 구할 때 이미 검출된 요소는 제거하면서 확인해야 한다.

 

2. 글자쌍을 제외하는 방식

처음엔 영문자 외의 문자가 들어간 경우 단순히 제거하는 줄 알고 처음에 바로 제거했다.

그러나 "aa+bb"같은 경우 

미리 제거하고 aabb로 처리시 => [aa, ab, bb] 이렇게 되어버린다.

문제가 요구하는 바대로

[aa, a+, +b, bb]로 쪼갠 후 영문자 외의 문자가 포함된 글자쌍을 제거하여 => [aa, bb]가 되어야 한다.

 

 

function solution(str1, str2) {

    // 대소문자 구분이 없으므로, 미리 소문자로 변환한다.
    const s1 = str1.toLowerCase();
    const s2 = str2.toLowerCase();

    // 영어 소문자만 검출하는 정규식
    var eng = /[a-z]/g;
    
    // 두글자씩 쪼개서 담는다. 이때, a+등 영문자가 아닌 문자가 포함된 글자쌍은 제외한다.
    const arr1 = [];
    const arr2 = [];
    for(let i =0;i<s1.length-1;i++) {
        const str = s1[i] + s1[i+1];
        if(str.replace(eng, '').length == 0) arr1.push(str);
    }
    for(let i =0;i<s2.length-1;i++) {
        const str = s2[i] + s2[i+1];
        if(str.replace(eng, '').length == 0) arr2.push(str);
    }

    console.log('sanitized: ', arr1, arr2);
    
    // 비교할 문자열이 없다면 유사도는 1이므로 바로 리턴한다.
    if(arr1.length ==0 && arr2.length==0) return 65536;
    
    // 동일한 배열인 경우에도 유사도가 1이다.
    arr1.sort();
    arr2.sort();
    if(JSON.stringify(arr1) == JSON.stringify(arr2)) return 65536;

    // 교집합
    // 주의할 점은 단순 unique 배열이 아니라 중복을 허용하는 배열이므로,
    // 찾은 요소를 제거해주어야 한다.
    const tempArr2 = JSON.parse(JSON.stringify(arr2));
    const intersection = arr1.reduce((acc,cur)=> {
        if(tempArr2.includes(cur)) {
            const index2 = tempArr2.indexOf(cur);
            tempArr2.splice(index2, 1);
            return [...acc, cur];
        } else {
            return acc;
        }
    },[]);
    
    // 합집합의 원소 갯수만 구하면 되므로, 집합1과 집합2의 갯수에서 교집합의 수만 빼면 된다.
    const union = arr1.length + arr2.length - intersection.length;
    return Math.floor(intersection.length/union*65536);
}

 

 

 

 

 

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