[CodeKata] 프로그래머스 : 3.24(수), 뉴스 클러스터링

🥋 Ooooth!! (Level 2)

 

🧮 풀이

10번 케이스에서만 실패가 발생했다.

const regex = /^[a-z]*$/; 

function solution(str1, str2) {
  str1 = str1.toLowerCase().split("").map((e,i,arr) => e = arr[i+1] && e + arr[i+1]).filter(e => e && regex.test(e)).sort()
  str2 = str2.toLowerCase().split("").map((e,i,arr) => e = arr[i+1] && e + arr[i+1]).filter(e => e && regex.test(e)).sort()

  let idx = -1;
  let common = [];
  for (let s of str1) {
    const strIdx = str2.findIndex((e, i) => i > idx && e === s);
    if (strIdx !== -1) {
      common.push(s)
    }
    idx = strIdx
  }
  const intersection = common.length
  const union = [...str1, ...str2].length - intersection

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

1. str1, str2 글자쌍 집합 가공

• 먼저, 대/소문자 구분을 없애기 위한 toLowerCase() 를 적용한다.
• 다음, slice()된 배열을 map()을 통해 2글자씩 쌍을 지어준다. 이를, filter() 와 정규식으로 알파벳 외 값을 포함한 요소들을 제거한다.
• 마지막으로 sort()를 하는데, 이 이유는 이후 교집합을 구할 시 한 쪽 글자쌍 집합의 인덱스 위치에 의존하기 때문이다.

2. intersection(교집합의 길이), union(합집합의 길이) 계산

• 다음으로, intersection(교집합의 길이)을 구해준다. common은 교집합 배열이며, idx는 현재까지 탐색한 인덱스 위치이다.
• str1을 순회하며, 1) str2에서 포함하는지와 2) 현재까지 탐색한 인덱스보다 큰 지 2가지 조건으로 인덱스를 탐색한다. (findIndex)
• 현재까지 탐색한 인덱스를 포함한 이유는, 일반적인 계산법으론 중복요소가 모두 포함되므로 중복된 갯수만큼만 걸러내기 위함이다.
• 탐색한 strIdx가 -1이 아니라면 해당 요소는 str1, str2의 교집합에 해당된다. 이를 common에 push, idx를 strIdx로 최신화한다.
• intersection은 교집합의 길이이므로 common.length, union(합집합의 길이)는 str1, str2를 합친뒤 교집합의 길이만 빼주면 된다.

3. 결과값 반환

• union이 0이면 분모가 0이 되어 NaN이 반환되므로, 문제와 같이 65536을 반환한다. 
• 나머지 경우는 자카드 유사도를 계산한 뒤, 65536을 곱해준다. 소수점을 버림하기 위해, Math.floor를 적용한다.

 

 

🖇 리뷰

케이스 4, 7, 9, 10, 11에서 오류가 발생했고, 이는 중복요소에 대한 처리에서 오류가 있어 발생한다는 문답이 많았다.

모범답안을 가져왔는데, 메우 직관적인 좋은 풀이여서 공유한다!!

 

function solution (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);
  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);
}

 

1. explode() 함수는 글자쌍 집합을 배열로 반환한다. text를 순회하며 2글자씩 자르고, 정규식에 일치하면 소문자로 담는다. 
2. set는 글자쌍 집합인 arr1, arr2 요소들을 중복 없이 담은 Set 자료형이다. 이를 순회하며, union, intersection 갯수를 센다.
3. set 각 요소들이 arr1, arr2에 몇 개씩 포함되어있는지 has1, has2를 계산한다. 더 작은 값을 intersection, 큰 값을 union에 더한다.