[JS] [1차] 뉴스 클러스터링

 

 

난이도: Lv. 2

문제: https://school.programmers.co.kr/learn/courses/30/lessons/17677

프로그래머스

 

 

알고리즘

1. 입력으로 들어온 두 문자열을 두 글자씩 끊어서 Object에 담는다. Object의 키-값 쌍은 해당 문자열이 몇 개 있는가를 나타낸다. 두 글자씩 끊었을 때 영문자가 아닌 글자가 포함되어 있는 문자열인 경우 Object에 담지 않고, 모두 영문자여서 Obejct에 담을 때는 소문자로 변경하여 담는다. 다중집합 원소를 비교할 때 대소문자의 차이를 구분하지 않는다고 했기 때문이다.

2. 첫 번째 Object의 key들을 순회하며 두 번째 Object에서 그 key를 가지고 있는지 확인한다.

2-1. 가지고 있는 경우 교집합에 해당하고, 다중집합일수 있음을 고려하여 두 Object의 key에 대한 value 중 더 작은 수를 intersection(교집합 원소의 개수를 나타내는 변수)에 더한다.

2-2. 가지고 있지 않다면 합집합에 해당하므로 union(합집합 원소의 개수를 나타내는 변수)에 value를 더한다.

3. 2.의 과정을 통해 교집합과 합집합에 해당하는 첫 번째 Object의 모든 원소들을 구분했다. 두 번째 Object의 원소들은 교집합에 대해서만 구분된 상태이다. 두 번째 Object의 원소들 중 합집합에만 해당하는 원소들은 교집합에 해당하는 원소들을 제외한 원소들이다. 따라서 두 번째 Object의 원소들 중 첫 번째 Object의 원소와 겹치지 않는 원소들의 value를 union에 더한다.

 

 

코드

const sliceString = (str) => {
    const strObj = {};

    for (let i = 0; i < str.length - 1; i++) {
        const regExp = /^[a-z|A-Z]+$/;
        const slicedStr = str.substring(i, i + 2).toLowerCase();
        if (regExp.test(slicedStr)) {
            if (Object.hasOwn(strObj, slicedStr)) { strObj[slicedStr]++; }
            else { strObj[slicedStr] = 1; }
        }
    }

    return strObj;
}

function solution(str1, str2) {
    let intersection = 0, union = 0;
    const strObj1 = sliceString(str1);
    const strObj2 = sliceString(str2);

    // calc intersection and union
    for (const key of Object.keys(strObj1)) {
        if (Object.hasOwn(strObj2, key)) {
            intersection += Math.min(strObj1[key], strObj2[key]);
            union += Math.max(strObj1[key], strObj2[key]);
        } else {
            union += strObj1[key];
        }
    }

    // calc union
    for (const key of Object.keys(strObj2)) {
        if (!Object.hasOwn(strObj1, key)) {
            union += strObj2[key];
        }
    }

    if (union === 0) { return 65536; }
    return Math.floor(intersection / union * 65536);
}

 

 

주저리

처음에 별 생각없이 문자열 쪼개서 배열에 넣어놓고 다중집합을 어떻게 처리할지 몰라서 멍 때리다가 Object로 풀어야 한다는 생각이 들어서 그렇게 했더니 한 번에 통과했다. 사실 교집합 합집합 처리도 한참 고민했는데 구현해 보면 별거 아닌데 너무 어렵게 생각했던 것 같다. 카카오 문제들은 길어서 문제 이해하는데도 시간이 좀 걸린다.