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

문제

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

주어진 문자열을 조건에 맞게 배열로 만든다.
두 배열의 교집합/합집합 * 65536을 구하는 문제

해결방법

1. 문자열을 주어진 조건에 맞게 만든다.
2. 각 배열의 합집합의 수, 교집합의 수를 구해서 나눠준다.

문자열을 조건에 맞는 배열로 바꾸기

영문외에 공백, 숫자, 특수문자는 들어가면 되지 않기 때문에 아스키코드를 이용해서 판별했다.

function checkString(char) {
  const charKey = char.toLowerCase().charCodeAt();
  return charKey >= 97 && charKey <= 122;
}

위의 함수를 이용해 소문자로 바꿔서 영문이 확인되면 배열에 추가해주었다.

for문을 돌면서 각 char을 검사해주는데 char과 그 다음에오는 char을 검사해줘야 되기 때문에 str1[i + 1] && checkString(str1[i]) && checkString(str1[i + 1]) 이라는 조건이 true가 되면 배열에 넣어줬다. (i는 for문에서의 index이다.)

합집합 교집합 수 구하기

일단 수 만 구하면 된다.

합집합의 수 = 각 배열의 모든 요소들 합 - 교집합의 수

이기 때문에 교집합만 구하면 되는 문제이다.

교집합 구하기

1. 주어진 문자열을 배열로만든 strFirstArr, strSecondArr을 이용해서 각각 객체로 만들어 주었다.
   (firstObj,secondObj)

key값은 요소이고 value값은 key값의 개수이다.

ex) ['aa','aa','bb'] => {'aa':2, 'bb':1}

2. 위 2개 중 하나의 객체를 선택해 순회하면서 같은 키값이 다른 객체에도 있다면 둘 중 작은 값만큼 교집합의 수 (interactionSize)에 더해주는 것으로 했다.

  for (let key in firstObj) {
    if (secondObj[key]) {
      interactionSize += Math.min(firstObj[key], secondObj[key]);
    }
  }

code

function solution(str1, str2) {
  let strFirstArr = [];
  let strSecondArr = [];
  for (let i = 0; i < str1.length; i++) {
    if (str1[i + 1] && checkString(str1[i]) && checkString(str1[i + 1])) {
      //대소문자가 같기 때문에 모두 소문자로 넣어준다.
      strFirstArr.push(str1[i].toLowerCase() + str1[i + 1].toLowerCase());
    }
  }
  for (let i = 0; i < str2.length; i++) {
    if (str2[i + 1] && checkString(str2[i]) && checkString(str2[i + 1])) {
      //대소문자가 같기 때문에 모두 소문자로 넣어준다.
      strSecondArr.push(str2[i].toLowerCase() + str2[i + 1].toLowerCase());
    }
  }
  let interactionSize = 0;
  let unionSize = 0;
  let firstObj = {};
  let secondObj = {};

  //교집합 구하기 위해 객체로 만들기
  strFirstArr.forEach((v) => {
    if (firstObj[v]) firstObj[v]++;
    else firstObj[v] = 1;
  });
  strSecondArr.forEach((v) => {
    if (secondObj[v]) secondObj[v]++;
    else secondObj[v] = 1;
  });
  // 중복되는걸 교집합으로 더해준다.
  for (let key in firstObj) {
    if (secondObj[key]) {
      interactionSize += Math.min(firstObj[key], secondObj[key]);
    }
  }

  //교집합을 이용해 합집합을 구해준다.
  unionSize = strFirstArr.length + strSecondArr.length - interactionSize;

  if (!strFirstArr.length && !strSecondArr.length) return 1 * 65536;
  else return Math.floor((interactionSize / unionSize) * 65536);
}

function checkString(char) {
  const charKey = char.toLowerCase().charCodeAt();
  return charKey >= 97 && charKey <= 122;
}

마무리

교집합을 구하는데 Map,Set을 이용해 보고 싶었지만 결국 편한 object로 구하게 됐다.

다른 사람이 푼 답안을 보니 Set을 사용하고, 카카오문제에서 제시했듯이 각요소가 있으면 min-교집합, max-합집합 으로 구한것을 보았다.

한번에 이해하기도 쉽고 카카오에서 제시한것을 이용해서 해결한것이 더 깔끔해보였다.

//set = strFirstArr, strSecondArr을 set으로 만든것
  set.forEach(item => {
    const has1 = arr1.filter(x => x === item).length;
    const has2 = arr2.filter(x => x === item).length;
    unionSize += Math.max(has1, has2);
    intersectionSize += Math.min(has1, has2);
  })

위의 코드처럼하면 보기에도 훨씬 깔끔하고 좋은 코드인것같다.

문제를 그냥 해결하는 것보다 효율적으로 해결하려는 능력을 연습해야 될것같다.