[Algorithm] [1차] 뉴스 클러스터링

문제 설명

[1차] 뉴스 클러스트링은 대부분 자카드 유사도에 대한 설명으로 두 개의 문자열을 받아 문자를 2개씩 자른 배열을 만든 후 두 배열의 자카드 유사도를 구한 후 65536을 곱하여 반환해야 한다.

자카드 유사도

자카드 유사도(Jaccard Similarity)는 두개의 집합 A,B가 있을 때 두 집합의 합집합 중 교집합의 비율을 의미한다.

문제 해결

배열을 사용한 문제풀이

1. 문자열의 다중집합 배열을 만드는 함수를 구현한다. 소문자로 변환한 두자리 문자열이 영문이면 배열에 포함시킨다.
2. str1의 다중집합 ngrams1을 순회하며 합집합에 모든 요소를 추가하고 ngrams2와의 중복 요소는 교집합에 추가한 후 ngrams2에서 중복 요소를 제거한다.
3. ngrams1과의 중복요소가 제거된 ngrams2를 union에 추가하여 어느 한쪽에라도 포함된 원소가 담긴 합집합을 만든다.
4. 교집합과 합집합의 요소의 길이가 0이라면 1을 아니라면 자카드 유사도 공식에 맞는 값을 반환한다.
5. 문제에서 요구하는 65536을 곱하여 정수로 내림한 값을 반환한다.

function solution(str1, str2) {
    
    function getNgrams(str) {
      const ngram = [];
      str = str.toLowerCase();
      for (let i = 0; i < str.length; i++) {
          const twoString = str.substring(i,i + 2);
          if (twoString.match(/[a-z]{2}/)) ngram.push(twoString);
      }        
        return ngram;
    }
    // 입력받은 문자열을 영문으로 이루어진 두개의 문자열 배열로 저장
    const ngrams1 = getNgrams(str1);
    const ngrams2 = getNgrams(str2);
    // 교집합과 합집합
    let intersection = [];
    let union = [];
    
    for (ngram of ngrams1) {
        if (ngrams2.includes(ngram)) {
            // 두 배열의 공통요소를 교집합에 추가
            const index = ngrams2.indexOf(ngram);
           intersection.push(ngram);
           //두 배열의 공통요소를 ngrams2에서 제거하면 ngrams2 = ngrams2 - ngrams1의 중복요소가 된다.
           ngrams2.splice(index,1);
        }
        // ngrams1의 모든 요소를 합집합에 추가한다.
        union.push(ngram);
    }
    
    //ngrams1의 중복요소 + 중복요소가 제거된 ngrams2를 합집합에 추가한다.
    union = [...union, ...ngrams2];
    
    // 교집합과 합집합의 길이가 0이면 1을, 아니라면 자카드 유사도 값을 가진다.
    let zzacard = [...union,...intersection].length === 0 ? 1 : intersection.length/union.length;
    return Math.floor((zzacard * 65536))
}
}

Map 객체를 사용한 문제풀이

Chat GPT가 제안한 코드로 키와 값의 쌍으로 저장되는 Map 객체를 사용하였다.
1. 영문의 2자리 문자를 Map 객체의 키로 저장한 후 참조된 횟수를 값으로 갖는다.
2. 두 문자열의 Map 객체를 구한 후 중복된 요소를 구하여 중복된 요소의 값이 더 작은 정수로 교집합의 갯수를 구한다.
3. 중복된 요소와 중복되지 않은 요소는 합집합에 더하여 두 배열 중 요소가 하나라도 포함된 합집합의 갯수를 구한다.
4. 중복되거나 중복되지 않는 요소가 없을 때, 1을 곱한 값을 반환하고 해당되지 않는다면 자카드 유사도 값에 65536을 곱하여 정수로 내림한 값을 반환한다.

function solution(str1, str2) {
    function getNgram(str) {
        const ngrams = new Map();
        str = str.toLowerCase();
        for (let i = 1; i < str.length; i++) {
            const twoString = str.slice(i - 1, i + 1);
            if (twoString.match(/[a-z]{2}/)) {
                ngrams.set(twoString, (ngrams.get(twoString) || 0) + 1);
            }
        }
        return ngrams;
    }

    const ngrams1 = getNgram(str1);
    const ngrams2 = getNgram(str2);

    let intersection = 0;
    let union = 0;

    // 수정된 부분: 두 문자열의 n-gram에서 교집합과 합집합 계산
    for (const [ngram, count] of ngrams1) {
        if (ngrams2.has(ngram)) {
            intersection += Math.min(count, ngrams2.get(ngram));
            union += Math.max(count, ngrams2.get(ngram));
        } else {
            union += count;
        }
    }

    for (const [ngram, count] of ngrams2) {
        if (!ngrams1.has(ngram)) {
            union += count;
        }
    }

    // 수정된 부분: 교집합과 합집합이 0인 경우 처리
    if (union === 0) {
        return 65536; // 두 문자열이 모두 공집합인 경우
    }

    return Math.floor((intersection / union) * 65536);
}
``