프로그래머스 [1차] 뉴스 클러스터링 JavaScript
2022년 12월 28일
입력 형식
- 입력으로는 str1과 str2의 두 문자열이 들어온다. 각 문자열의 길이는 2 이상, 1,000 이하이다.
- 입력으로 들어온 문자열은 두 글자씩 끊어서 다중집합의 원소로 만든다. 이때 영문자로 된 글자 쌍만 유효하고, 기타 공백이나 숫자, 특수 문자가 들어있는 경우는 그 글자 쌍을 버린다. 예를 들어 "ab+"가 입력으로 들어오면, "ab"만 다중집합의 원소로 삼고, "b+"는 버린다.
- 다중집합 원소 사이를 비교할 때, 대문자와 소문자의 차이는 무시한다. "AB"와 "Ab", "ab"는 같은 원소로 취급한다.
출력 형식
입력으로 들어온 두 문자열의 자카드 유사도를 출력한다. 유사도 값은 0에서 1 사이의 실수이므로, 이를 다루기 쉽도록 65536을 곱한 후에 소수점 아래를 버리고 정수부만 출력한다.
풀이
구현 문제로 생각하고 필요 기능을 하나씩 구현했다.
- function multisetElement(str): 문자열을 두 글자씩 끊어서 다중집합을(array) 만들어 반환하는 함수
- function dictionaryCreate(arr): array를 dictionary로 변환해서 반환하는 함수
- function intersection(dic1, dic2, dic1Key, dic2Key): dic1 과 dic2의 교집합의 길이를 반환하는 함수
- dic1Key의 한 키값이 dic2Key에도 있을 때 dic1과 dic2에 그 키의 아이템들 중 작은 값을 더해 준다.
- function union(dic1, dic2, dic1Key, dic2Key): dic1과 dic2의 합집합의 길이를 반환하는 함수
- dic1Key의 한 키값이 dic2Key에도 있을 때 dic1과 dic2에 그 키의 아이템들 중 큰 값을 더해 준다.
- dic1Key의 한 키값이 dic1Key에만 있을 때 dic1의 그 키 아이템만 더해주고, dic2key도 똑같이 더해준다.
solution.js
function solution(str1, str2) {
let answer = 0;
const str1Set = multisetElement(str1);
const str2Set = multisetElement(str2);
const str1Dic = dictionaryCreate(str1Set);
const str2Dic = dictionaryCreate(str2Set);
const dic1Key = Object.keys(str1Dic);
const dic2Key = Object.keys(str2Dic);
if (dic1Key.length === 0 && dic2Key.length === 0) {
answer = 65536;
}
else {
const intersectionNum = intersection(str1Dic, str2Dic, dic1Key, dic2Key);
const unionNum = union(str1Dic, str2Dic, dic1Key, dic2Key);
answer = Math.floor((intersectionNum / unionNum) * 65536);
}
return answer;
}
// 문자열 다중 집합 원소화
function multisetElement(str){
const regex = /^[a-z|A-Z]+$/;
const multiset = new Array();
const strLength = str.length;
for (let i = 0; i < strLength-1; i++) {
let left = str[i];
let right = str[i+1];
if (regex.test(left) && regex.test(right)) {
left = left.toUpperCase();
right = right.toUpperCase();
multiset.push(left+right);
}
}
return multiset;
}
// arr to dic
function dictionaryCreate(arr){
const dic = {};
for (let i = 0; i < arr.length; i++) {
arr[i] in dic === true ? dic[arr[i]] += 1 : dic[arr[i]] = 1;
}
return dic;
}
// 교집합
function intersection(dic1, dic2, dic1Key, dic2Key) {
let intersectionNum = 0;
for(let i = 0; i < dic1Key.length; i++) {
if (dic2Key.includes(dic1Key[i])) {
const dic1KeyNum = dic1[dic1Key[i]];
const dic2KeyNum = dic2[dic1Key[i]];
dic1KeyNum < dic2KeyNum === true ? intersectionNum += dic1KeyNum : intersectionNum += dic2KeyNum;
}
}
return intersectionNum;
}
// 합집합
function union(dic1, dic2, dic1Key, dic2Key) {
let unionNum = 0;
for (let i = 0; i < dic1Key.length; i++) {
if (dic2Key.includes(dic1Key[i])) {
const dic1KeyNum = dic1[dic1Key[i]];
const dic2KeyNum = dic2[dic1Key[i]];
dic1KeyNum > dic2KeyNum === true ? unionNum += dic1KeyNum : unionNum += dic2KeyNum;
}
else {
unionNum += dic1[dic1Key[i]];
}
}
for (let i = 0; i < dic2Key.length; i++) {
if (dic1Key.includes(dic2Key[i]) === false) {
unionNum += dic2[dic2Key[i]];
}
}
return unionNum;
}