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

in 코딩테스트 on 프로그래머스




뉴스 클러스터링

프로그래머스

나의 풀이

function solution(str1, str2) {
  const getMultiSet = str => {
    let elements = [];
    str = str.toUpperCase();
    for (let i = 0; i < str.length - 1; i++) {
      elements.push(str[i] + str[i + 1]);
    }
    return elements.filter(v => !/[^A-Za-z]/.test(v));
  };

  const str1MultiSet = getMultiSet(str1);
  const str2MultiSet = getMultiSet(str2);

  const getIntersection = (arr1, arr2) => {
    for (let i = 0; i < arr1.length; i++) {
      for (let j = 0; j < arr2.length; j++) {
        if (arr1[i] === arr2[j]) {
          arr1[i] = true;
          arr2[j] = true;
          continue;
        }
      }
    }
    return arr1.filter(v => v === true).length;
  };

  const interserction = getIntersection(str1MultiSet, str2MultiSet);
  const union = str1MultiSet.length + str2MultiSet.length - interserction;

  return interserction === 0 && union === 0 ? 65536 : Math.floor((interserction / union) * 65536);
}
  • getMultiSet 함수로 다중집합을 구한다.
  • getIntersection 함수로 교집합의 갯수를 구한다.
  • 자카드 유사도를 구한 뒤 리턴한다.
  • 집합 A와 집합 B 모두 공집합일 때 J(A, B) = 1을 이해하지 못해서 삽질을 했다.
  • 모두 공집합인 경우는 교집합 === 0 && 합집합 === 0 인 경우다. (나는 처음에 교집합===0 만 처리해서 에러가 났다.)


best 코드

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);
}

교집합을 구하기 위해 이중for문을 짠 게 마음에 안들었는데(getIntersection),
이분은 set을 통해 구현하셨다.