풀이
/**
* 뉴스클러스터링.js
* https://programmers.co.kr/learn/courses/30/lessons/17677?language=javascript
*/
function solution(str1, str2) {
const arr1 = sliceByTwo(str1); // 1
const arr2 = sliceByTwo(str2); // 1
return Math.floor(getJaccardSimilarity(arr1, arr2) * 65536); // 2, 3
}
function sliceByTwo(str) {
const upStr = str.toUpperCase();
const arr = [];
for (let i = 0; i < upStr.length - 1; i++) {
const slicedStr = upStr.slice(i, i + 2);
if (slicedStr.match(/[^A-Z]/g) === null) arr.push(slicedStr); // 1-1
}
return arr;
}
function getJaccardSimilarity(arr1, arr2) { // 2
let intersectionNum = 0, unionNum = 0;
const hash1 = arr1.reduce(makeHash, {}); // 2-1
const hash2 = arr2.reduce(makeHash, {}); // 2-1
const inter = getUniqueIntersection(arr1, arr2); // 2-2
const union = getUniqueUnion(arr1, arr2); // 2-3
inter.forEach((item) => {
intersectionNum += Math.min(hash1[item] ? hash1[item] : 0, hash2[item] ? hash2[item] : 0); // 2-4
});
union.forEach((item) => {
unionNum += Math.max(hash1[item] ? hash1[item] : 0, hash2[item] ? hash2[item] : 0); // 2-5
});
if (intersectionNum === unionNum) return 1; // 2-6
return intersectionNum / unionNum; // 2-7
}
function getUniqueIntersection(arr1, arr2) {
return [...new Set(arr1.filter((str) => arr2.indexOf(str) > -1))]; // 2-2
}
function getUniqueUnion(arr1, arr2) {
return [...new Set([...arr1, ...arr2])]; // 2-3
}
function makeHash(obj, str) { // 2-1
if (!obj[str]) {
obj[str] = 1;
} else {
obj[str]++;
}
return obj;
}
- 파라미터로 넘겨받은 str1 과 str2 를 주어진 조건에 맞게 2글자씩 잘라서 array 로 만들어주는 함수인 sliceByTwo 에 넘겨 배열로 만들어준다.
- 1-1. 문제에 주어진 조건 중, 영문자로 된 글자 쌍 이외엔 모두 버리는 내용이 있으므로 정규표현식을 통해 알파벳 이외의 내용이 있는 글자 쌍을 걸러준다. 모든 알파벳은 대문자로 변경했으므로 정규표현식에서도 대문자 알파벳만 확인해준다.
- 자카드 유사도를 구하기 위해 만든 함수 getJaccardSimilarity 함수에 1에서 만들어준 arr1, arr2를 넘겨준다.
- 2-1. 각 값의 개수를 저장하는 hash1과 hash2를 넘겨받은 arr1, arr2 를 기반으로 만들어준다. 추후 교집합과 합집합을 만들어준 이후 그 안의 값들의 개수를 셀 때 사용하기 위함이다.
- 2-2. 교집합을 만들되 문제에선 aa와 aa 가 2개씩 있을 경우 교집합도 당연히 aa, aa 가 2개 다 들어가는데, getUniqueIntersection 함수에선 우선 aa, aa 가 2개씩 있더라도 공통으로 있는건 Set 을 통해 하나만 남도록해준다. 갯수는 추후 2-1 에서 만들어준 hash를 통해 계산해준다.
- 2-3. 합집합을 만들되 마찬가지로 겹치는 내용은 하나로 계산해서 합집합을 계산해준다. 여기서도 Set을 사용한다.
- 2-4. 2-1에서 만든 hash1과 hash2를 사용해 교집합에 존재하는 값들의 개수 중 더 작은 값을 intersectionNum에 더해준다. aa가 str1엔 3개 str2엔 2개 있었다면 당연히 교집합에서 aa는 2개인 원리다. undefined 인 경우를 삼항연산자를 통해 0으로 예외처리해준다.
- 2-5. 합집합도 교집합과 원리는 같되 합집합에 존재하는 값들의 개수 중 더 큰 값을 unionNum에 더해준다. 마찬가지로 aa가 str1엔 3개 str2엔 2개 있었다면 합집합에서 aa는 3개인 원리다. undefined 인 경우를 삼항연산자를 통해 0으로 예외처리해준다.
- 2-6. 예외처리를 위한 내용이다. 교집합과 합집합의 개수가 0인 경우 자카드 유사도가 0 나누기 0 으로 NaN이 나오게된다. 이를 방지하기 위해 교집합과 합집합의 값이 같은 경우 자카드 유사도를 1로 반환해준다.
- 2-7. 2-6 이외의 경우 교집합 개수 나누기 합집합 개수 의 값을 반환한다.
- 돌려받은 자카드 유사도 값에 문제에서 주어진대로 65536 을 곱해주고 소수점 아래 값을 버린 뒤 반환하면 끝난다.
댓글