[Javascript] 1차 뉴스 클러스트링 (17677)

문제링크

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

 

접근 방법

배열이 아닌 Hash Table을 사용해보기 위해 Map 객체를 적용해보았다.

먼저 주어진 문자열 str1, str2을 대문자로 변환하고 2글자씩 자른 문자를 담을 Map 객체를 만들었다.

const sliceStr = (str, strMap) => {
    const regChar = /[A-Z]/;
    for(let i = 0; i<str.length-1; i++){
        if(regChar.test(str[i]) && regChar.test(str[i+1])){
            const subStr = str.substr(i,2);
            strMap.has(subStr) ? strMap.set(subStr, strMap.get(subStr)+1) : strMap.set(subStr, 1);   
        }
    } 
}​

주어진 문자열을 대문자일 경우만 2글자씩 자르는 함수이다.
정규식이 true(test 사용)일 때만 str의 substr(index, 개수)를 잘라 Map에 담는다.

(3항 연산자를 이용한 Map 객체에 key와 value를 넣는 방법을 사용하였다.)


다음으로 합집합의 원소 수와 교집합의 원소 수를 담을 변수를 선언하고 str2Map을 기준으로 집합을 채웠다.

for(let s2Cnt of str2Map.values()) unionCnt += s2Cnt;

str2Map의 values의 모든 값을 우선 합집합에 더함.

for(let s1 of str1Map){
    const [str, cnt] = s1;
    if(str2Map.has(str) && str2Map.get(str) >= str1Map.get(str)) intersectionCnt += cnt;
    else if(str2Map.has(str) && str2Map.get(str) < str1Map.get(str)) {
        intersectionCnt += str2Map.get(str);
        unionCnt += (str1Map.get(str) - str2Map.get(str))
    }
    else unionCnt += cnt;
}

 다음으로 str1Map의 값들을 통해 나머지 집합을 채웠다.

if(str2Map.has(str) && str2Map.get(str) >= str1Map.get(str)) intersectionCnt += cnt;

1. 만약 str1Map의 str이 str2Map에 있고 str2Map의 str 수가 str1Map의 str 수보다 크거나 같을 때.
즉, "AB"란 문자가 str2Map에는 2개, str1Map에는 1개가 있을 때 1개만큼 더한다.

else if(str2Map.has(str) && str2Map.get(str) < str1Map.get(str)) {
    intersectionCnt += str2Map.get(str);
    unionCnt += (str1Map.get(str) - str2Map.get(str))
}

 2. 만약 str1Map의 str이 str2Map에 있고 str1Map의 str 수가 str2Map의 str 수보다 작을 때.
즉, "AB"란 문자가 str2Map에는 1개, str1Map에는 2개가 있을때 
 2.1 교집합에는 더 작은 값인 str2Map.get(str)의 수 만큼 더한다.
 2.2 합집합에는 아까 str2Map의 "AB"인 1이 들어갔는데, str1Map에 2개가 있으므로
        str1Map.get(str) (2개) - str2Map.get(str) (1개) 만큼 추가 해준다.

else unionCnt += cnt;

3. 만약 str1Map의 str이 str2Map에는 없을 때,
합집합에 str1Map의 cnt만큼 추가해준다.

이렇게 합집합(union)과 교집합(intersection)의 수를 구했으므로 둘을 나누고 65536을 곱하여 소수점을 제거하면 된다.

(예외처리 => 합집합, 교집합의 수가 모두 0일 경우 65536을 반환한다.)

function solution(str1, str2) {
    var answer = 0;
    let str1Map = new Map();
    let str2Map = new Map();
    str1 = str1.toUpperCase()
    str2 = str2.toUpperCase()

    sliceStr(str1, str1Map);
    sliceStr(str2, str2Map);
    
    let intersectionCnt = 0;
    let unionCnt = 0;
    for(let s2Cnt of str2Map.values()) unionCnt += s2Cnt;
    for(let s1 of str1Map){
        const [str, cnt] = s1;
        if(str2Map.has(str) && str2Map.get(str) >= str1Map.get(str)) intersectionCnt += cnt;
        else if(str2Map.has(str) && str2Map.get(str) < str1Map.get(str)) {
            intersectionCnt += str2Map.get(str);
            unionCnt += (str1Map.get(str) - str2Map.get(str))
        }
        else unionCnt += cnt;
    }
    
    
    if(unionCnt === 0) return 65536;
    
    answer = Math.floor((intersectionCnt / unionCnt) * 65536)
    
    return answer;
}

const sliceStr = (str, strMap) => {
    const regChar = /[A-Z]/;
    for(let i = 0; i<str.length-1; i++){
        if(regChar.test(str[i]) && regChar.test(str[i+1])){
            const subStr = str.substr(i,2);
            strMap.has(subStr) ? strMap.set(subStr, strMap.get(subStr)+1) : strMap.set(subStr, 1);   
        }
    } 
}