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

뉴스 클러스터링

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

함수 분리하기에 최적의 문제였던 듯. 일단 고생했던 곳은 교집합을 구하는 함수와 차집합을 구하는 함수의 과정이 똑같아서 분리하기가 애매했기 때문에 임의로 합쳐놨는데 뭔가 찜찜..
그리고 array.push()의 반환값이 넣은 값인 줄 알았는데 인덱스여서.. 와.. 정말 쌩 기초를 모르고 있었구나 생각했다. 이거때문에 막바지에 엄청 고생했다.
그리고 또 고민해야할 것은.. 정렬문제! 여긴 딱히 정렬에 엄격하지 않아서 그냥 A의 차집합, B의 차집합, 교집합을 그냥 합쳐줘서 순서가 엉망인데 만약 정렬이 필요했다면 더 고민해야 할 듯.
그리고 시간복잡도.. 시간복잡도는... 생각 안할래... 엉엉...

수도코드

1. 문자열을 분리하는 함수

• 인자 : 문자열
• 조건 1. 알파벳만 가능할 것
• 조건 2. 대소문자 구분 x
• 리턴 : 두 글자씩 끊은 집합의 배열

2. 교집합을 구하는 함수

• 인자 : 집합1, 집합2
• 조건 : 다중집합 포함
• 리턴 : 교집합

3. 합집합을 구하는 함수

• 인자 : 집합1, 집합2
• 리턴 : 합집합

4. 자카드 유사도를 구하는 함수

• 인자: (교집합, 합집합)
• 리턴: Math.floor((교집합 / 합집합) * 65536);

풀이

function solution(str1, str2) {
    // 각 문자열을 집합으로 분리한다
    let setA = makeSet(str1);
    let setB = makeSet(str2);
    
    // 두 집합의 합집합과 교집합을 구한다
    let intersection = getDifferenceOrIntersection(setA, setB, true);
    let sumOfSets = getSumOfSets(setA, setB);
    
    // 자카드 유사도를 출력한다.
    return getJaccardSimilarity(intersection, sumOfSets);
}

// 문자열을 분리하는 함수
function makeSet(str) {
    let set = [];
    
    for (let i = 0; i < str.length - 1; i++) {
        let curLetter = str[i];
        let nextLetter = str[i + 1];
        
        let checkEng = /[a-zA-Z]/;
        if (checkEng.test(curLetter) && checkEng.test(nextLetter)) {
            set.push(curLetter.toUpperCase() + nextLetter.toUpperCase());
        };
    }
    return set;
}

// 교집합을 구하는 함수 (겸사겸사 차집합도 구한다)
function getDifferenceOrIntersection(setA, setB, isIntersection) {
    let differenceA = setA.slice()
    let differenceB = setB.slice()
    let intersection = [];
    
    for (let i = 0; i < differenceB.length; i++) {
        if (differenceA.includes(differenceB[i])) {
            intersection.push(differenceB[i]);
            let commonIndex = differenceA.findIndex(el => el === differenceB[i]);
            differenceA.splice(commonIndex, 1)
        }
    }
    return isIntersection ? intersection : differenceA;
}

// 합집합을 구하는 함수
function getSumOfSets(setA, setB) {
    let differenceA = getDifferenceOrIntersection(setA, setB);
    let differenceB = getDifferenceOrIntersection(setB, setA);
    let intersection = getDifferenceOrIntersection(setA, setB, true);
    return [...differenceA, ...differenceB, ...intersection];
}

// 자카드 유사도를 구하는 함수
function getJaccardSimilarity(intersection, sumOfSets) {
    let interLength = intersection.length;
    let sumLength = sumOfSets.length;
    let jaccard = !interLength && !sumLength ? 1 : interLength / sumLength;
    return Math.floor(jaccard * 65536);
}

이제 다른 사람 코드 보러 가야징

다른 사람 풀이

1. 오.. 이 분은 Map으로 푸셨는데 넘나 신박.. https://allo-ew.tistory.com/108
2. 이 분은 교집합과 합집합을 한 번에 계산하셨다.. 오.... https://jongbeom-dev.tistory.com/154