[알고리즘 JS] 뉴스 클러스터링(프로그래머스 Lv.2)

문제

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

프로그래머스

풀이

// 조건에 따라 다중 집합을 만드는 함수
function getMultiSet(str) {
  str = str.toUpperCase();
  str = str
    .split('')
    .map((s, i) => s + str[i + 1])
    .filter(set => set.match(/[A-Z]{2,}/g));

  return str;
}

// 원소의 갯수가 카운팅된 객체를 만드는 함수
function getMap(arr) {
  const arrMap = {};

  arr.forEach(el => {
    if (arrMap[el]) {
      arrMap[el]++;
    } else {
      arrMap[el] = 1;
    }
  });

  return arrMap;
}

function solution(str1, str2) {
  const str1Arr = getMultiSet(str1);
  const str2Arr = getMultiSet(str2);

  const str1Map = getMap(str1Arr);
  const str2Map = getMap(str2Arr);

  // 두 문자열에 등장하는 전체 원소를 구한다.
  const keys = new Set([...Object.keys(str1Map), ...Object.keys(str2Map)]);

  let intersection = 0;
  let union = 0;

  // 전체 원소를 하나씩 반복한다.
  for (let key of keys) {
    // 두 문자열에 모두 포함된 경우
    if (str1Map[key] && str2Map[key]) {
      // 교집합에는 공통으로 포함되는 값(최소값)
      intersection += Math.min(str1Map[key], str2Map[key]);
      // 합집합에는 교집합을 포함하는 값(최대값)
      union += Math.max(str1Map[key], str2Map[key]);
    }
    // 어느 한 문자열에만 포함되는 원소는 등장하는 횟수를 각각 합집합에 합산
    else if (str1Map[key]) {
      union += str1Map[key];
    } else if (str2Map[key]) {
      union += str2Map[key];
    }
  }

  // 교집합, 합집합이 둘 다 공집합인 경우 예외처리
  return !intersection && !union
    ? 65536
    : Math.floor((intersection / union) * 65536);
}

• 다중집합이 유니크한 집합이 아닌 중복을 허용하는 집합이라 교집합, 합집합을 구하는 과정이 조금 어려웠다.
• 정규 표현식 : 대문자로 문자열 변환 후 길이 2 까지의 문자열만을 집합의 원소로 포함해야해서 정규 표현식을 사용했다. /[A-Z]{2,}/g 이렇게 썼는데, 지금보니 숫자 2 다음 쉼표가 들어갈 필요가 없다.
• 각 집합에 원소의 종류와 갯수가 몇 개 있는지 카운팅하는 객체를 만들었다.
• 두 집합의 전체 원소의 종류를 Set 객체를 활용해서 구하고, 이를 하나씩 돌면서 교집합과 합집합을 구했다.
• 교집합을 구할 땐 공통원소인지 확인하여 최솟값을 넣으면 되고, 공통 원소의 합집합의 경우 교집합을 포함하기 때문에 둘 중 갯수가 많은 쪽을 합산하면 된다. 
• 두 집합 중 한 집합에만 해당하는 원소의 경우 해당 원소의 갯수를 합집합에 합산한다.

다른 사람의 풀이

function ref(str1, str2) {
  function explode(text) {
    const result = [];
    for (let i = 0; i < text.length - 1; i++) {
      const node = text.substr(i, 2);
      if (node.match(/[A-Za-z]{2}/)) {
        result.push(node.toLowerCase());
      }
    }
    return result;
  }

  const arr1 = explode(str1);
  const arr2 = explode(str2);
  // 전체 원소를 파악하기 위해 set 객체 생성
  // 내 풀이의 경우 객체의 키값을 사용했는데, 이렇게 하면 굳이 Object.keys 로 확인할 필요 없음.
  const set = new Set([...arr1, ...arr2]);
  let union = 0;
  let intersection = 0;

  set.forEach(item => {
    const has1 = arr1.filter(x => x === item).length;
    const has2 = arr2.filter(x => x === item).length;
    // 각 집합에서 원소 갯수의 최댓값
    // 어차피 최댓값이기 때문에 한 쪽이 원소를 가지고 있지 않다고해도 합집합에 정확히 합산됨
    union += Math.max(has1, has2);
    // 최솟값 합산
    intersection += Math.min(has1, has2);
  });
  return union === 0 ? 65536 : Math.floor((intersection / union) * 65536);
}

• 나의 경우 객체에서 키값을 추출해 set 객체를 만들었는데, 두 다중 집합을 set 하면 두 집합에 속해있는 전체 원소를 구할 수 있기 때문에 더 효율적인 방법인 것 같다. 
• 또 set 을 토대로 교집합, 합집합을 구할 때 포함된 경우를 확인하지 않고 max 값과 min 값을 비교해주면, 원소가 존재하지 않는 경우 길이가 0이기 때문에 합산에 문제가 없다.