프로그래머스 뉴스클러스터링 (카카오 기출)

이정수·2024년 10월 30일

https://tech.kakao.com/posts/344

문제 설명

이 문제는 자카드 유사도 J(a,b) 를 설명해주고 자카드유사도 값을 직접 계산하는 프로그램을 작성하는 문제이다.

자카드 유사도를 구하는 공식은 간단하다. 교집합을 합집합으로 나눈 수이다. 이 값은 늘 0~1사이의 실수가 되므로 65536을 곱한 후 소수점 아래를 버리고 정수부분만 취하도록 한다.

문제 설명은 원소의 중복을 허용하는 다중집합으로 되어 있다. 자주 접하는 자료구조가 아니여서 이부분이 어려웠다. 카카오 테크블로그의 문제해설에서는 다중집합 자료구조를 사용하지 않고 각 원소를 정렬된 배열에 넣어 병합정렬 코드를 응용하여 교집합과 합집합 함수를 구현하는 방법이 있다고 한다.

결론적으로는 주어진 문자열로 다중집합을 만들고, 각 집합의 교집합, 합집합을 구현해내는것이 관건인 문제였다.

몇가지 예외 케이스로는

A,B가 모두 공집합일 경우 J(A,B)는 1로 고정한다.
A,B중 교집합이 공집합이고 합집합이 공집합이 아닌 경우 0을 반환한다.(분자 부분만 0이므로)

집합의 원소가 될 문자쌍은 다음과 같이 만든다.

문자열 "FRANCE"와 "FRENCH"가 주어졌을 때, 이를 두 글자씩 끊어서 다중집합을 만들 수 있다. 각각 {FR, RA, AN, NC, CE}, {FR, RE, EN, NC, CH}

이를 바탕으로 교집합, 합집합을 만든다.

교집합은 {FR, NC}, 합집합은 {FR, RA, AN, NC, CE, RE, EN, CH}

자카드 유사도를 구한다.

J("FRANCE", "FRENCH") = 2/8 = 0.25

그 외의 주의해야 할 규칙으로는

알파벳을 제외한 문자열 쌍은 버린다.
알파벳 대소문자를 구분하지 않는다.(A,a는 같은 값이다.)

구현 Flow

주어진 문자열로 가능한 모든 집합의 요소를 만든다.
- 필요없는 쌍은 버린다. → 모듈화
교집합을 구한다.
합집합을 구한다.
자카드 유사도를 구한다.
65536을 곱하고 소숫점을 버린다.

구현 방식

1. 집합을 Map 형태로 변환

자카드 유사도를 계산하기 위해 각 집합의 원소갯수를 알아야 한다.
Set 자료형은 중복을 혀용하지 않는다.

위 두가지 이유로 key: value 형태의 Map자료형을 활용하여 문자쌍:갯수 형태로 저장한다.

예를들어 {1,1,1,2,2,3}의 경우 { 1:3, 2:2, 3:1 } 이 된다.

2. 모듈화

반복되는 작업이 많으므로 코드를 줄이기 위해 세부기능을 모듈화 하였다.

주어진 문자열로 가능한 모든 문자쌍을 만든다.

function makeCharPair(str) {
  const arr = [];
  for (let i = 0; i < str.length - 1; i++) {
    arr.push(str1.slice(i, i + 2));
  }
  return arr;
}

필요없는 쌍은 버리고, 유효한 집합 요소만 return

function removeInvalidChar(arr) {
  const regex = /[^a-zA-Z]/;
  return arr.filter(elem => !regex.test(elem));
}

문자열 쌍 배열에서 요소별 등장횟수를 카운트해서 map 형태로 반환한다.

function countOccurency(arr) {
  const map = new Map();

  arr.forEach(el => {
    map.set(el, (map.get(el) || 0) + 1); //NOTE
  });
  return map;
}

교집합 구하기

function getIntersection(map1, map2) {
  const intersectionMap = new Map();
  // NOTE : MAP순회
  map1.forEach((value1, key) => {
    // 교집합의 값이 있다면
    if (map2.has(key)) {
      // 더 적게 등장한 갯수를
      intersectionMap.set(key, Math.min(value1, map2.get(key)));
    }
  });
  return intersectionMap;
}

합집합 구하기

function getUnion(map1, map2) {
  // return new Map([...map1, ...map2]); 이렇게 단순 합치면 테케 통과x
  let union = new Map();

  for (let [key, value] of map1.entries()) {
    union.set(key, value);
  }

  for (let [key, value] of map2.entries()) {
    if (map1.has(key)) {
      // 겹치는 값이 있다면 큰 쪽을 택한다.
      union.set(key, Math.max(value, map1.get(key)));
    } else {
      union.set(key, value);
    }
  }
  return union;
}

각 모듈을 조합한 전체 solution함수는

function solution(strA, strB) {
  const str1 = strA.toLowerCase();
  const str2 = strB.toLowerCase();

  // 주어진 문자열로 가능한 모든 문자쌍을 만든다.
  let arr1 = makeCharPair(str1);
  let arr2 = makeCharPair(str2);

  //필요없는 문자쌍은 버린다.
  arr1 = removeInvalidChar(arr1);
  arr2 = removeInvalidChar(arr2);

  // 각 배열별 요소의 등장 횟수를 저장한다.
  let map1 = countOccurency(arr1);
  let map2 = countOccurency(arr2);

  // 둘다 공집합인경우
  if (map1.size === 0 && map2.size === 0) {
    return 65536;
  }

  // 교집합을 구한다.
  const intersection = getIntersection(map1, map2);
  // 합집합을 구한다.
  const union = getUnion(map1, map2);

  // 교집합이 0이면 0
  if (intersection.size === 0 && union.size > 0) {
    return 0;
  }

  const intersectionSize = [...intersection.values()].reduce((a, c) => a + c);
  const unionSize = [...union.values()].reduce((a, c) => a + c);

  // 실수 -> 정수부만 취하기
  return ~~((intersectionSize / unionSize) * 65536);
}

배운점

정규식 사용
- 알파벳으로만 이루어진 경우인지 검증해야 했다. 정규식외에 다른 구현방법이 떠오르지 않았다.
- regex.test(elem) 메서드
||의 활용
- (map.get(el) || 0) + 1
  - map에서 el 키값이 있을 경우 value +1
  - 없을경우 1
map의 순회방식
- forEach : 각 요소에 대해 콜백함수를 수행
  - map1.forEach((value1, key) => {}) :Value가 먼저 온다!
- for .. of 루프
  - map.entries(): 키 & 값
```
for (let [key, value] of map1.entries()) {
    union.set(key, value);
  }
```
  - map.keys() : 키 Only
```
for (const key of myMap.keys()) {
console.log(Key: ${key});
}
```
  - map.values() : 값 Only
```
for (const value of myMap.values()) {
console.log(Value: ${value});
}
```
- 맵을 배열로 바꿔서 순회 : Array.from(map) 혹은 전개연산자 [ … map ]
Set, Map, 배열의 간단한 차이
- Set: 순서 X, 중복 X, 값
- 배열 : 순서 O, 중복 O, 값
- Map : 키값은 고유, 키: value

이정수

keep on pushing

이전 포스트