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

뉴스 클러스터링 - 프로그래머스

 

문제링크

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

 

 

문제복기

 

다중집합과 자카드 유사도에 대한 개념이 나온다.

개념은 모두 지문에서 알려주지만, 다중집합을 구현하는 것은 어렵지 않았지만

다중집합 간에 교집합과 합집합을 구하는 부분에서 어려움을 느꼈다.

 

 

뉴스 클러스터링 - 문제풀이

 

---

 

1단계

1단계에서는 두 문자열의 다중집합을 구현하는 로직을 작성한다.

다중집합을 우선 생성해야 교집합과 합집합을 구하고, 자카드 유사도를 구할 수 있기 때문이다.

뉴스 클러스터링 - 1단계

 

 

다중집합을 생성하는 로직은 아래의 코드와 같이 구현했다.

반복문을 돌면서 하나씩 붙여주고, 알파벳이 아닌 문자는 continue하는 방식으로 구현했다. 

마지막으로 대소문자 구분이 없는 점을 고려해주었다.

// 다중집합 생성 함수
const makeMultiSet = str => {
    const result = [];
    for (let i = 0; i < str.length - 1; i++) {
        const word = str[i] + str[i + 1];
        // 알파벳이 아닌 문자 포함 여부 확인
        if (/[^a-zA-Z]/.test(word)) continue;
        result.push(word.toLowerCase()); // 대소문자 구분 제거
    }
    return result;
};

 

 

다중집합 multiSet1, multiSet2를 구할 수 있었다.

 

---

2단계

교집합과 합집합을 구하는 단계이다.

multiSet1, multiSet2 중에 하나는 온전히 나둔다. 아래의 코드는 multiSet1을 온전히 union 배열에 복사를 한다.

 

multiSet1을 순회하면서 multiSet2의 복사본인 copyMultiSet2에서 동일한 word가 존재한다면(index !== -1)

intersection 배열(교집합 배열)에 push하고 copyMultiSet2에서 제거한다.

// 교집합 계산
const intersection = [];
const union = [...multiSet1];

const copyMultiSet2 = [...multiSet2]; // multiSet2를 수정하면서 작업
multiSet1.forEach(word => {
    const index = copyMultiSet2.indexOf(word);
    if (index !== -1) {
        intersection.push(word);
        copyMultiSet2.splice(index, 1); // 이미 교집합에 포함된 원소는 제거
    }
});

// 합집합 계산 (남은 multiSet2 추가)
union.push(...copyMultiSet2);

 

왜 제거할까? 

union에 남은 copyMultiSet2를 다 합해주면 합집합이 되기 때문이다.

 

---

3단계

자카드 유사도만 지문대로 구하면 끝이다.