[programmers] 뉴스 클러스터링 (in JS)
문제
뉴스 클러스터링 - 2020 kakao blind recruitment
주어진 두 스트링에서 각각 다중집합을 구하고, n(교집합) / n(합집합)으로 자바드 유사도를 구하는 ㅁ누제이다.
Fact
- 두 다중 집합이 공통적으로 갖고 있는 원소들을 알게 되면, 다중집합의 교집합과 합집합을 구할 수 있다.
접근
- 두 스트링의 다중 집합을 구한다.
- 두 다중집합이 공통적으로 갖고 있는 원소들을 구한다.
- 두 다중집합이 2에서 구한 각 원소들을 각자 집합에서 몇 개를 갖고 있는지 구한다.
- 그 값들로 교집합의 크기와 합집합의 크기를 구한다.
- 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);
}
Author And Source
이 문제에 관하여([programmers] 뉴스 클러스터링 (in JS)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yejineee/programmers-뉴스-클러스터링-in-JS저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)