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

문제 링크

• 자카드 유사도 사용 : 두 집합 A, B 사이의 자카드 유사도는 두 집합의 교집합 크기를 두 집합의 합집합 크기로 나눈 값
• 자카드 유사도 사용시 모두 공집합인 경우 1
• 2 이상 1,000 이하의 문자열 str1, str2
• str1, str2에는 중복요소가 있음
• 문자열을 두글자씩 끊어서 다중집합의 원소로 생성.
  영문자로 된 글자쌍만 유효, 그 외의 문자는 버림
  ('ab+c'의 경우 'ab', 'b+', '+c' 중 유효한 요소는 'ab'만)
• 문자열의 대소문자 차이는 무시
• J(str1, str2) * 65536 return (단 소수점 아래는 버리고 정수부분만 출력)

function solution(str1, str2) {
    // str1과 str2를 대문자 통일, 배열화
    // 맵으로 두글자씩 배열화하기. 
    str1 = str1.toUpperCase();
    str2 = str2.toUpperCase();
    const arr1 = []
    const arr2 = []
    // 영문자로 된 글자쌍 확인을 위한 정규표현식
    const regex = /[a-zA-Z]/
    
    for(let i = 0; i<Math.max(str1.length, str2.length)-1; i++){
      	// 둘 중 글자수가 많은 쪽을 기준으로 돌기 때문에 적은 쪽은 undefined 발생
      	// 해당 위치의 글자와 다음 글자가 undefined가 아니면서 정규표현식을 통과한 조건
        if(str1[i+1] && regex.test(str1[i]) && regex.test(str1[i+1])){
            arr1.push(str1.slice(i, i+2))
        }
        if(str2[i+1] && regex.test(str2[i]) && regex.test(str2[i+1])){
            arr2.push(str2.slice(i, i+2))
        }
    }
  
  	// 합집합의 크기를 먼저 구하기
    const all = [...arr1, ...arr2].length;
    // 중복을 허용하므로 교집합을 구할 때 이미 구한 요소는 제거해야 함
    let intersection = 0; // 교집합의 크기
    arr1.forEach((ele)=>{
        const include = arr2.indexOf(ele)
        if(include >= 0){
            intersection += 1;
            arr2.splice(include, 1)
        }
    })
    const unionArr = all-intersection;
    if(!intersection && !unionArr) return 65536;
    return Math.floor((intersection / unionArr)*65536)
}

교집합 : let difference = arr1.filter(x => arr2.includes(x));
차집합 : let difference = arr1.filter(x => !arr2.includes(x));
처음에는 자바스크립트에서 교집합과 차집합을 구하는 공식을 찾아서 사용했는데, 그랬더니 예제 입출력은 모두 통과할 수 있었으나 str1 = "BAAAA", str2 = "AAA" 처럼 중복되는 경우 문제 발생
(arr1 = ['BA','AA','AA','AA'], arr2= ['AA','AA'],
교집합은 ['AA','AA']가 되어야 하지만 위 공식을 사용하면 ['AA','AA','AA']가 되어 원하는 답이 나오지 않게 된다)
때문에 splice를 이용, 비교가 일어날 때마다 요소를 제거하는 방식으로 바꿔야 모든 케이스가 통과됨

다른 사람의 풀이

function solution (str1, str2) {
  function explode(text) {
    const result = [];
    for (let i = 0; i < text.length - 1; i++) {
      const node = text.substr(i, 2);
      if (node.match(/[A-Za-z]{2}/)) {
        result.push(node.toLowerCase());
      }
    }
    return result;
  }

  const arr1 = explode(str1);
  const arr2 = explode(str2);
  const set = new Set([...arr1, ...arr2]);
  let union = 0;
  let intersection = 0;

  set.forEach(item => {
    const has1 = arr1.filter(x => x === item).length;
    const has2 = arr2.filter(x => x === item).length;
    union += Math.max(has1, has2);
    intersection += Math.min(has1, has2);
  })
  return union === 0 ? 65536 : Math.floor(intersection / union * 65536);
}

str1과 str2로 배열을 구하는 과정을 함수로 해 재사용성이 좋게 만들고, 정규표현식에 {2} 조건을 추가하여 if조건을 훨씬 간단하게 만들었다.