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

아래 프로그래머스 로고를 클릭하면 해당 문제로 이동합니다 😀

풀이과정

---

구현 아이디어는 다음 로직을 따라가면 된다.
1. 입력 문자열 전처리 : 문자열에서 영문자 쌍만 추출(python에선 isalpha(), js에서는 정규식 사용)하고, 모두 대문자로 변환해서 비교한다.
2. 다중집합 만들기 -> 두 글자씩 잘라 유효한 쌍만 Counter에 저장
3. 교집합과 합집합 구하기(&, | 연산자 사용)
4. 자카드 유사도 계산 -> 교집합 원소 수 / 합집합 원소 수
5. 결과 출력

코드

---

1. Python

from collections import Counter

def make_multiset(s):
    s = s.upper()
    multiset = []
    
    for i in range(len(s) - 1):
        pair = s[i:i+2]
        if pair.isalpha():
            multiset.append(pair)
    return Counter(multiset)
    
    
def solution(str1, str2):
    multiset1 = make_multiset(str1)
    multiset2 = make_multiset(str2)
    
    inter = sum((multiset1 & multiset2).values())
    union = sum((multiset1 | multiset2).values())
    
    if union == 0:
        return 65536
    return int(inter / union * 65536) 

2. JS

function makeMultiset(str) {
  const multiset = new Map();
  str = str.toUpperCase();

  for (let i = 0; i < str.length - 1; i++) {
    const pair = str[i] + str[i + 1];
    if (/^[A-Z]{2}$/.test(pair)) {
      multiset.set(pair, (multiset.get(pair) || 0) + 1);
    }
  }
  return multiset;
}

function solution(str1, str2) {
  const multiset1 = makeMultiset(str1);
  const multiset2 = makeMultiset(str2);

  let intersectionSize = 0;
  let unionSize = 0;
  const allKeys = new Set([...multiset1.keys(), ...multiset2.keys()]);

  for (const key of allKeys) {
    const count1 = multiset1.get(key) || 0;
    const count2 = multiset2.get(key) || 0;
    intersectionSize += Math.min(count1, count2);
    unionSize += Math.max(count1, count2);
  }

  if (unionSize === 0) {
    return 65536;
  }

  return Math.floor((intersectionSize / unionSize) * 65536);
}

결과

---