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

문제

코드를 FRANCE와 FRENCH가 주어졌을 때, 이를 두 글자씩 끊어서 다중집합을 만들 수 있다. 
각각 {FR, RA, AN, NC, CE}, {FR, RE, EN, NC, CH}가 되며, 교집합은 {FR, NC}, 합집합은 {FR, RA, AN, NC, CE, RE, EN, CH}가 되므로, 두 문자열 사이의 자카드 유사도 J("FRANCE", "FRENCH") = 2/8 = 0.25가 된다.

입력 형식
1. 입력으로는 str1과 str2의 두 문자열이 들어온다. 
2. 각 문자열의 길이는 2 이상, 1,000 이하이다.
3. 입력으로 들어온 문자열은 두 글자씩 끊어서 다중집합의 원소로 만든다. 
이때 영문자로 된 글자 쌍만 유효하고, 기타 공백이나 숫자, 특수 문자가 들어있는 경우는 그 글자 쌍을 버린다. 
예를 들어 ab+가 입력으로 들어오면, ab만 다중집합의 원소로 삼고, b+는 버린다.
다중집합 원소 사이를 비교할 때, 대문자와 소문자의 차이는 무시한다. AB와 Ab, ab는 같은 원소로 취급한다.입력하세요

출력 형식
입력으로 들어온 두 문자열의 자카드 유사도를 출력한다. 
유사도 값은 0에서 1 사이의 실수이므로, 이를 다루기 쉽도록 65536을 곱한 후에 소수점 아래를 버리고 정수부만 출력한다.

코드

function solution(str1, str2) {
    var answer = 0;
    let arr1 = getStrArr(str1);
    let arr2 = getStrArr(str2);
    let intersection = getIntersection(arr1, arr2);
    let union = getUnion(arr1, arr2, intersection);

    (intersection.length === 0 && union.length === 0) ? answer = 1 
        : answer = intersection.length/union.length;

   return Math.floor(answer*65536);
}

function getStrArr(str){
    let arr = [];
    for(let i=0; i<str.length-1; i++){
        let sliceStr = str.substr(i, 2).toLowerCase();
         /[^a-z]|\s/.test(sliceStr) ? ''
         : arr.push(sliceStr);
        
    }
    return arr;
}

function getIntersection(arr1, arr2){
    let intersection = [];
    let taget = JSON.parse(JSON.stringify(arr2));
    for(let i=0; i<arr1.length; i++){
        let idx = taget.findIndex(a=>{return a===arr1[i]});
        if(idx >= 0){
            intersection.push(taget.splice(idx, 1)[0]);
        }
    }
    return intersection;
}

function getUnion(arr1, arr2, intersection){
    let concatArr = arr1.concat(arr2);
    for(let i=0; i<intersection.length; i++){
        let idx = concatArr.findIndex(c=>{return c===intersection[i]});
        if(idx >= 0){
            concatArr.splice(idx, 1);
        }
    }
    return concatArr;

}

방법

  1. 문자열을 2글자씩 잘라 공백, 특수문자가 있는 문자열은 버림(arr1, arr2)
  2. arr1, arr2의 교집합과 합집합을 찾음
    2-1. '문자 자체'는 중복허용
    2-2. 그래서 교집합에 중복된 문자가 있지만 이를 다르게 취급
  3. 교집합 구하기
    3-1. arr1, arr2를 비교하여 같은 문자를 splice하여 intersection 배열에 추가함
  4. 합집합 구하기
    4-1. arr1, arr2를 합친 배열에서 intersection에 속한 문자를 삭제

후기

  • 2-1, 2-2 중복땜에 교집합, 합집합 구하는 것에 시간이 오래걸려서 짜증..
  • 집합이 필요한 것이 아니라 집합의 길이 를 구하는 것이기 때문에 더 좋은 방법이 있을 것 같음
  • 분모&&분자 모두 0일 때를 문제에서 말하고있어 함정이 있었음

좋은 웹페이지 즐겨찾기