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

두 문자열을 두 글자씩 끊어서 만든 다중집합의 자카드 유사도를 구하는 문제였다.

자세한 문제 설명은 아래로!
https://programmers.co.kr/learn/courses/30/lessons/17677

자카드 유사도?

두 집합의 교집합의 크기 / 두 집합의 합집합 크기
a,b 집합 모두 공집합일 땐 1

아이디어

• 문자열을 대문자로 변환한다.
• 들어오는 문자열을 두글자씩 끊어서 집합을 만든다.
  - 영문자(대소구분없음)만 유효하고 다른 기호들은 조합하지 않는다.
• 두 집합의 교집합의 갯수와 합집합의 갯수를 구한다.
• 리턴값 = 자카드 유사도 * 65536의 정수(소수점 버림)

풀이

교집합을 구할 때 교집합의 개수는 두 집합 중에 원소의 개수가 적은 집합의 개수보다 적거나 같기 때문에 크기가 작은 집합을 순회하며 다른 집합에도 포함되어 있는지 검사해준다. 이때, 다른 집합에 원소가 포함되어 있다면 splice로 원소를 빼주는 것이 포인트였던 것 같다.

function solution(str1, str2) {
    str1 = str1.toUpperCase()
    str2 = str2.toUpperCase()
    let table = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    let arr1 = []
    let arr2 = []
    
    //str1, str2에서 나올 수 있는 원소 만들기 
    for(let i=0; i<str1.length; i++) {
        if(table.includes(str1[i]) && table.includes(str1[i+1])) {
            arr1.push(`${str1[i]}${str1[i+1]}`)
        }
    }
    for(let i=0; i<str2.length; i++) {
        if(table.includes(str2[i]) && table.includes(str2[i+1])) {
            arr2.push(`${str2[i]}${str2[i+1]}`)
        }
    }
   //console.log(arr1, arr2)
    
    //두 집합의 교집합 구하는 함수
    const intersaction = (a1, a2) => {
        if(a1.length > a2.length) {
            let temp = a1
            a1 = a2
            a2 = temp
        }
        let output = []
        a1.forEach((el, idx) => {
            if(a2.includes(el)) {
                let findIdx = a2.indexOf(el)
                a2.splice(findIdx, 1)
                output.push(el)
            }
        })
        return output.length
    }
    //교집합 갯수
    let inter = intersaction(arr1, arr2)
  
    //합집합 구하기 => 두 집합 - 두 집합의 교집합
    //교집합 만들 때 이미 두 집합의 중복 값들은 제외함
    let union = arr1.concat(arr2).length
    console.log(inter, union)
    
    if(inter === 0 && union === 0) return 65536
    else return parseInt(inter / union * 65536)
}