1️⃣ 문제 설명

코딩테스트 연습 - [1차] 뉴스 클러스터링

2️⃣ 풀이

// 자카드 유사도
// 두 집합 A, B 사이의 자카드 유사도
// J(A, B)는 두 집합의 교집합 크기를 두 집합의 합집합 크기로 나눈 값
// 모두 공집합일 경우에는 나눗셈이 정의되지 않으니 J(A, B) = 1

// 중복을 허용하는 다중집합에 대해서 확장 가능

// 1. 문자열 파싱
// 두 글자씩 끊어서 다중 집합의 원소로 만든다
// 영문자로 된 글자 쌍만 유효하고, 기타 공백 숫자 특문은 글자 쌍을 버림
// 대소문자 차이는 무시
// 자카드 유사도는 0~1이므로, 65536을 곱한 후 소수점 아래 버림

// 2. 중복이 없는 합집합 만들기

// 3. 합집합의 요소들을 파싱된 문자열과 비교하며 일치하는 문자열 개수 구하기

// 4. 개수 중 큰 값을 중복 합집합, 작은 값을 중복 교집합에 추가한다

3️⃣ 나의 코드

function solution(str1, str2) {
	const parsedStr1 = parse(str1);
	const parsedStr2 = parse(str2);
	//set을 사용하여 중복이 없는 합집합 생성
	const union = new Set([...parsedStr1, ...parsedStr2]);
	let overlappedUnion = 0;
	let overlappedIntersection = 0;

	union.forEach((str) => {
		const count1 = parsedStr1.filter((v) => v === str).length;
		const count2 = parsedStr2.filter((v) => v === str).length;
		overlappedUnion += Math.max(count1, count2);
		overlappedIntersection += Math.min(count1, count2);
	});

	if (overlappedUnion === 0) return 65536;

	return ((overlappedIntersection / overlappedUnion) * 65536) >> 0;
}

//문자열 파싱 함수
function parse(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;
}

4️⃣ 마무리

중복을 허용한다는 부분에서 많이 헤맸던 문제

처음엔 단순히 교집합, 합집합을 생각해서 쉽게 풀릴 줄 알았는데, 중복을 어떻게 처리할 지를 생각해내느냐 많은 시간이 소요됐다

마지막에 max, min을 쓰는 부분은 사실 얻어 걸린 부분이어서 다시 한 번 볼 필요가 있다

하지만 다시 보고싶지 않은 문제다