91. [1차] 뉴스 클러스터링 Javascript

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

프로그래머스

 

1. 문제에 대한 이해

• 우리가 풀어야 할 문제는 무엇인가?
   - 입력으로 들어온 두 문자열의 자카드 유사도에 65536을 곱한 후 소수점 아래를 버린 정수값을 구하라
• 주어진 자료는 무엇인가?
   - str1과 str2의 두 문자열
• 조건은 무엇인가?
   - 각 문자열의 길이는 2 이상, 1,000 이하이다.
   - 입력으로 들어온 문자열은 두 글자씩 끊어서 다중집합의 원소로 만든다. 이때 영문자로 된 글자 쌍만 유효하고, 기타 공백이나 숫자, 특수 문자가 들어있는 경우는 그 글자 쌍을 버린다. 예를 들어 "ab+"가 입력으로 들어오면, "ab"만 다중집합의 원소로 삼고, "b+"는 버린다.
   - 다중집합 원소 사이를 비교할 때, 대문자와 소문자의 차이는 무시한다. "AB"와 "Ab", "ab"는 같은 원소로 취급한다.
• 숨겨진 조건이나 자료가 있는가? 그렇다면 그 것을 다른 방법으로 해석해보라. 
   - 교집합과 합집합은 중복 허용이다.
   - 특수문자나 숫자를 제거할때는 먼저 문자열을 다 2개씩 나눈 다음에 처리해야한다.

2. 계획

1. 주어진 문자열에서 대문자를 소문자로 바꾼다.
2. 주어진 문자열을 단어 두개씩 잘라서 새로운 배열에 넣는다
   
3. 숫자나 특수문자가 있으면 배열에서 지운다. 
   
4. 이 두 배열의 교집합을 구한다. 
5. 이 두 배열의 합집합을 구한다.
6. 나누고 65536 곱하고 소수점 버려서 리턴

3. 실행

• 풀이 계획을 실행하고, 각 단계가 올바른지 점검하라.

const solution = (str1, str2) => {
  //   주어진 문자열에서 대문자를 소문자로 바꾼다.
  const newStr1 = str1.toLowerCase();
  const newStr2 = str2.toLowerCase();

  // 주어진 문자열을 단어 두개씩 잘라서 새로운 배열에 넣는다
  let arrStr1 = [];
  let arrStr2 = [];

  for (i = 0; i < newStr1.length; i++) {
    if (newStr1.slice(i, i + 2).length === 2) {
      arrStr1.push(newStr1.slice(i, i + 2));
    }
  }

  for (i = 0; i < newStr2.length; i++) {
    if (newStr2.slice(i, i + 2).length === 2) {
      arrStr2.push(newStr2.slice(i, i + 2));
    }
  }

  // 숫자나 특수문자가 있으면 배열에서 지운다. 
  const newArr1 = arrStr1.map(it => it.replace(/[^a-zA-Z]/g, "")).filter(it => it.length === 2);
  const newArr2 = arrStr2.map(it => it.replace(/[^a-zA-Z]/g, "")).filter(it => it.length === 2);

  if (newArr1.length === 0 || newArr2.length === 0) {
    return 65536;
  }

  // 이 두 배열의 교집합을 구한다.
  let intersection = 0;
  const set = [...new Set([...newArr1, ...newArr2])];
  set.forEach((it) => {
    const arr1 = newArr1.filter(e => e === it).length;
    const arr2 = newArr2.filter(e => e === it).length;
    intersection += Math.min(arr1, arr2);
  })

  // 이 두 배열의 합집합
  const union = newArr1.length + newArr2.length - intersection;

  // 나누고 65536 곱하고 소수점 버려서 리턴 
  return Math.floor((intersection / union) * 65536);
};

test('news', () => {
  expect(solution('FRANCE', 'french')).toEqual(16384);
  expect(solution('handshake', 'shake hands')).toEqual(65536);
  expect(solution('aa1+aa2', 'AAAA12')).toEqual(43690);
  expect(solution('E=M*C^2', 'e=m*c^2')).toEqual(65536);
});

 

코드 리팩터링 후 

const solution = (str1, str2) => {
  //   주어진 문자열에서 대문자를 소문자로 바꾼다.
  const newStr1 = str1.toLowerCase();
  const newStr2 = str2.toLowerCase();

  // 주어진 문자열을 단어 두개씩 잘라서 새로운 배열에 넣는다
  let arrStr1 = [];
  let arrStr2 = [];

  for (i = 0; i < newStr1.length; i++) {
    if (newStr1.slice(i, i + 2).length === 2) {
      arrStr1.push(newStr1.slice(i, i + 2));
    }
  }

  for (i = 0; i < newStr2.length; i++) {
    if (newStr2.slice(i, i + 2).length === 2) {
      arrStr2.push(newStr2.slice(i, i + 2));
    }
  }

  // 숫자나 특수문자가 있으면 배열에서 지운다. 
  const newArr1 = arrStr1.map(it => it.replace(/[^a-zA-Z]/g, "")).filter(it => it.length === 2);
  const newArr2 = arrStr2.map(it => it.replace(/[^a-zA-Z]/g, "")).filter(it => it.length === 2);

  if (newArr1.length === 0 || newArr2.length === 0) {
    return 65536;
  }

  // 이 두 배열의 교집합을 구한다.
  // 이 두 배열의 합집합
  let intersection = 0;
  let union = 0;
  const set = [...new Set([...newArr1, ...newArr2])];
  set.forEach((it) => {
    const arr1 = newArr1.filter(e => e === it).length;
    const arr2 = newArr2.filter(e => e === it).length;
    intersection += Math.min(arr1, arr2);
    union += Math.max(arr1, arr2);
  })

  // 나누고 65536 곱하고 소수점 버려서 리턴 
  const result = Math.floor((intersection / union) * 65536);
  return result;
};

 

 

문자열을 나누고 숫자랑 특수문자를 제거했어야했는데 
처음에 숫자랑 특수문자를 제거하고 문자열을 나눠서 풀었더니 테스트를 하나도 통과 못했다.

그래서 처음에 대문자를 소문자로 바꾸고 문자열을 2개씩 잘라서 새로운 배열에 넣어줬다. 
그 후에 정규식을 사용해서 특수문자와 숫자를 제거했고 제거 후에 문자열의 길이가 2인것만 남겨줬다.
공집합일 경우를 고려해서 문자열을 담은 배열의 길이가 각각 0이면 65536을 리턴해주는 예외처리를 해줬다.

교집합을 구하는 부분이 어려웠는데 , 두 배열을 합해서 중복을 전부 제거한 배열을 하나 만들었고 
중복 제거한 배열과 두 배열에서 일치하는 요소들을 filter로 걸러준 다음에 그 길이를 각각 구했다.
교집합의 길이는 이 두 배열의 길이 중에서 최소값이고 
합집합의 길이는 두 배열의 길이를 더한 값에서 교집합의 길이를 뺀 값이다.

이제 서로 나누고 65536을 곱한다음에 소수점을 버린 값을 리턴해주면 된다. 

교집합 구하는 부분을 코드로 구현하고 나니까 합집합도 한꺼번에 구할 수 있겠다는 생각이 들었다. 
합집합의 길이는 이 두 배열의 길이 중에서 최대값이므로 합집합의 길이 구하는 로직을 다시 써서 리팩터링 했다.