[programmers] 뉴스 클러스터링 (in JS)

문제

뉴스 클러스터링 - 2020 kakao blind recruitment

주어진 두 스트링에서 각각 다중집합을 구하고, n(교집합) / n(합집합)으로 자바드 유사도를 구하는 ㅁ누제이다.

Fact

• 두 다중 집합이 공통적으로 갖고 있는 원소들을 알게 되면, 다중집합의 교집합과 합집합을 구할 수 있다.

접근

1. 두 스트링의 다중 집합을 구한다.
2. 두 다중집합이 공통적으로 갖고 있는 원소들을 구한다.
3. 두 다중집합이 2에서 구한 각 원소들을 각자 집합에서 몇 개를 갖고 있는지 구한다.
4. 그 값들로 교집합의 크기와 합집합의 크기를 구한다.
   • 4에서 구한 값이 각각 a, b라고 하자.
   • 교집합의 크기는 min(a, b)이고, 합집합은 max(a, b)이다.
   • 합집합은 교집합을 제외 했을 때의 두 다중 집합의 크기를 더해주어야 한다.

복잡도

• 공간 복잡도 : O(N)
• 시간 복잡도 : O(N)
  • 입력의 문자열의 길이에 맞춰 한 번 순회한다.

알게된 점

• Number.prototype.toFixed()는 소수점 이하가 길면 반올림한다.
• Math.floor()는 주어진 숫자와 같거나 작은 정수 중에서 가장 큰 수를 반환하므로 -> 정수를 반환한다.

코드

const isAlpha = (x) => "a" <= x.toLowerCase() && "z" >= x.toLowerCase();
const getMultiSet = (str) => {
  const strArr = Array.from(str).map((s) => s.toLowerCase());
  const multiSet = strArr.reduce((multi, cur, i) => {
    if (i >= strArr.length - 1) {
      return multi;
    }
    const next = strArr[i + 1];
    if (!isAlpha(cur) || !isAlpha(next)) {
      return multi;
    }
    multi.push(cur + next);
    return multi;
  }, []);
  return multiSet;
};

const getResult = (num) => Math.floor(num * 65536);

const getIntersection = (arr1, arr2) => {
  const set1 = new Set(arr1);
  const intersection = arr2.reduce((interSet, element) => {
    if (set1.has(element)) {
      interSet.add(element);
    }
    return interSet;
  }, new Set());
  return [...intersection];
};

const countElement = (arr, value) => arr.filter((x) => x === value).length;

const countSetNotIntersection = (arr, intersection) => {
  const interSet = new Set(intersection);
  const filtered = arr.filter((elem) => !interSet.has(elem));
  return filtered.length;
};

function solution(str1, str2) {
  const multiSet1 = getMultiSet(str1);
  const multiSet2 = getMultiSet(str2);
  if (multiSet1.length === 0 && multiSet2.length === 0) {
    return getResult(1);
  }
  const intersectionArr = getIntersection(multiSet1, multiSet2);
  const baseUnion =
    countSetNotIntersection(multiSet1, intersectionArr) +
    countSetNotIntersection(multiSet2, intersectionArr);
  const { nIntersection, nUnion } = intersectionArr.reduce(
    (count, element) => {
      const countElemIn1 = countElement(multiSet1, element);
      const countElemIn2 = countElement(multiSet2, element);
      count.nIntersection += Math.min(countElemIn1, countElemIn2);
      count.nUnion += Math.max(countElemIn1, countElemIn2);
      return count;
    },
    { nIntersection: 0, nUnion: baseUnion }
  );
  return getResult(nIntersection / nUnion);
}