Skip to content

Latest commit

 

History

History
93 lines (69 loc) · 4.53 KB

42.md

File metadata and controls

93 lines (69 loc) · 4.53 KB

[1차] 뉴스 클러스터링

Set Operator를 구현할 수 있는가? + 실수 기록!

위 문제는 집합 연산자, 합집합, 교집합을 구현할 수 있는가에 대한 질문으로 이해할 수 있었다. 파이썬같은 언어에서는 Set 자료구조 안에 합집합과 교집합 (+ 차집합 등)에 대한 연산자가 빌트인으로 주어진다. 그러나 자바스크립트에서는 이것이 따로 주어지지 않아서 만약에 이런식으로 사용하고 싶다면, 따로 구현해서 사용해야하긴한다. 어쨌거나 위 문제는 이러한 연산자의 개념을 어떻게 잘 문제에 맞게 구현해서 사용할 것인가가 포인트인 문제였다.

Try1

입력되는 문자열에는 소문자/대문자/특수문자/공백이 모두 들어올 수 있다. 여기서 원문자열에서 두 글자씩 잘랐을 때를 부분 문자열이라고 하는데, 그 부분 문자열이 알파벳으로만 되어있는 경우에만 부분집합으로 처리한다고 되어있다.

그래서 나는 알파벳으로만 되어있는 문자열로 변환 후에 부분문자열을 만들 생각을 하였다. 그런데 이렇게 하면 문제의 요구 조건에 맞지 않는다는걸 알게 되었다. 나의 생각과 문제의 요구조건이 왜 다른지 예시를 보면 정확히 알 수 있었다.

문자열1 aa1+aa2
문자열2 AAAA12

  1. 나의 생각

    • 알파벳으로 구성된 문자열로 파싱 + toLowerCase()
      • 문자열1 : aaaa
      • 문자열2 : aaaa
    • 부분 문자열로 분리
      • 문자열1 : {aa, aa, aa}
      • 문자열2 : {aa, aa, aa}

  2. 문제의 요구조건

    • 부분 문자열로 분리
      • 문자열1 : {aa, a1, 1+, +1, aa, a2}
      • 문자열2 : {AA, AA, AA, A1, 12 }
    • 알파벳으로만 구성된 문자열 찾기 + toLowerCase()
      • 문자열1 : {aa, aa}
      • 문자열2 : {aa, aa, aa}

어떤 작업을 먼저하냐에 따라서 만들어지는 부분 문자열의 집합이 다르다는 것을 알게되었다.

Try2

function solution(str1, str2) {
  const multiSet1 = [];
  const multiSet2 = [];
  for (let i = 0; i < str1.length - 1; i++) {
    const sub = str1.slice(i, i + 2).toLowerCase();
    if (!sub.match(/[^a-z]/g)) multiSet1.push(sub);
  }
  for (let i = 0; i < str2.length - 1; i++) {
    const sub = str2.slice(i, i + 2).toLowerCase();
    if (!sub.match(/[^a-z]/g)) multiSet2.push(sub);
  }

  const intersection = [];
  for (let i = 0; i < multiSet1.length; i++) {
    if (multiSet2.includes(multiSet1[i])) {
      intersection.push(multiSet1[i]);
      const index = multiSet2.indexOf(multiSet1[i]);
      multiSet2.splice(index, 1);
    }
  }

  const union = multiSet1.concat(multiSet2);

  if (intersection.length === 0 && union.length === 0) return 65536;

  return Math.floor((intersection.length / union.length) * 65536);
}

두 번의 for문(이중for문 X)으로 부분 문자열을 만든 후에, 이를 토대로 교집합과 합집합을 위와 같이 만들 수 있었다. 단 여기서 주의할 점이 있었다. 원래 교집합을 구하는 코드가 아래와 같았다. (체크박스 부분이 추가 되었었음) 그런데 이렇게 하면 문제가 생긴다. splice는 원배열을 수정하기 때문에 현재 for문을 순회하고 있는 multiSet1의 길이가 동적으로 변하게되어 인덱스가 내가 예측한대로 동작하지 않는 경우가 생긴다.

예를 들어서 배열 길이 2인 multiSet1을 순회한다고 하자. 그리고 공통된 요소가 있어서 multiSet1에서 splice를 했다면, multiSet1의 길이가 1로 변경되면서 더이상 순회하지 않게된다. 사실은 multiSet1의 마지막 요소는 순회하지 않은 상태인데도 말이다. 이러한 오류때문에 multiSet1은 변경하지 않고 multiSet2만을 변경하게 되었다.

const intersection = [];
for (let i = 0; i < multiSet1.length; i++) {
  if (multiSet2.includes(multiSet1[i])) {
    intersection.push(multiSet1[i]);
    const index = multiSet2.indexOf(multiSet1[i]);
    multiSet1.splice(i, 1); // ✅
    multiSet2.splice(index, 1);
  }
}

위 코드의 원래 의도는

  • 교집합을 구한다
  • multiSet1과 multiSet2에서 교집합을 뺀다 → 결국 둘의 대칭 차집합을 구하는격!

이러하였다. 그런데 위와 같은 오류로 인해서 multiSet2에서만 교집합을 제거함으로서 multiSet2의 차집합을 구하게 변경하였다.

그래서 결론적으로 코드에서 보이다 싶이, 교집합은 intersection 배열, 합집합은 multiSet1와 multiSet2를 합한 배열이 된다.