programmers. 뉴스클러스터링

문제

문제

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

풀이

처음에 문제를 읽었을 때 엄청 쉬워보였다

우선 2글자씩 나누어서 배열에 넣고 문자 외의 것이 존재하는 원소는 빼버린 뒤에

교집합, 합집합을 구해서 연산만 하면되니까..

실제로 문제도 그러했지만 원소의 중복을 허용하는 다중집합이라는 부분에서 굉장히 시간을 많이 잡아먹었다

숫자로 만든 간단한 예제를 하나 보면

특수문자를 제거하고 2글자씩 추출한 배열 str1, str2가 다음과 같이 존재한다

str1 = [1,2,3,4,4,4];

str2 = [4,4,5,6,7,8,8];

이 때 합집합은 [1,2,3,4,4,4,5,6,7,8,8]이고 교집합은 [4,4]가 되는데 이부분을 구현하는데 애를 먹었다

내가 구현한 방법은 이러한데

1. 두 문자열을 정렬한 후에
2. 두 배열의 제일 첫 원소를 비교한다
3. 두 원소 중에 빠른 원소를 빼서 합집합 배열에 집어넣는다
4. 두 원소가 같다면 둘 다 빼주고 합집합엔 한 번만 집어넣는다
5. 두 배열 중 하나가 빌 때까지 2~4번을 반복
6. 하나의 배열의 길이가 0이 되면 나머지 배열을 모두 합집합 배열에 넣는다

써놓고 보니 비효율적인 것 같은데.. 아마 다른 방법이 있을 것 같다

교집합도 저런식으로 구했다가 두 집합의 크기를 더한 후 합집합에서 빼버리면 교집합 크기가 나온다는 걸 깨닫고 호다닥 지웠다

학교다닐 때 공부 좀 할걸

코드

function solution(str1, str2) {
    let arr1 = splitStr(str1);
    let arr2 = splitStr(str2);

    arr1 = removeSp(arr1).sort();
    arr2 = removeSp(arr2).sort();

    if(arr1.length===0&& arr2.length===0) return 65536;

    //교집합
    const interCnt = intersection(arr1,arr2);

    //합집합
    const unionCnt = arr1.concat(arr2).length - interCnt;

    return Math.floor((interCnt/unionCnt)*65536);
}
function removeSp(arr){
    return arr.filter(v=>v.search(/[^a-z]/gi)<0);
}

function intersection(arr11,arr22){
    const interArr = [];
    const arr1 = [...arr11];
    const arr2 = [...arr22];

    while(arr1.length&& arr2.length){
        if(arr1[0] < arr2[0]){
            arr1.shift();
        } else if (arr1[0] > arr2[0]){
            arr2.shift();
        } else {
            interArr.push(arr1.shift());
            arr2.shift();
        }
    }
    return interArr.length;

}

function splitStr(str){
    str = str.toLowerCase();
    const arr = [];
    for(let i=0; i+1<str.length;i++){
        arr.push(str.slice(i,i+2));
    }
    return arr;
}

문제를 풀어놓고 포스팅을 하다보니 코드를 보니 고칠점이 꽤 보인다

removeSp함수를 사용한 후에 sort하는게 반복되면 removeSp함수 내부에서 sort를 한 후 반환한다던지

변수명을 좀 신경써서 짓던지..