[JS] 2018 KAKAO BLIND RECRUITMENT[1차] > 뉴스 클러스터링

function making(str){
    
    str = str.split("").map((v,i)=>{if(i+1 < str.length) return str[i]+str[i+1]});
    
    //undefined 제거
    if(str[str.length-1] == undefined){
        str = str.slice(0, str.length-1);
    }
    
    //특문,숫자 포함 요소 제거 + 소문자로 변경
    str = str.filter(v => (/[a-zA-Z]{2}/g).test(v)).map(v=>v.toLowerCase());
    
    return str;
}

function solution(str1, str2) {

    str1 = making(str1);
    str2 = making(str2);

    if(str1.length == 0 && str2.length == 0){
        return 65536;
    }
    
    //교집합 개수 구하기
    var same = 0;
    
    for(var i = 0; i < str1.length; i++){
        for(var j = 0; j < str2.length; j++){
            
            if(str1[i] == str2[j]){
                same++;
                str2[j] = "";
                break;
            }
        }
    }
    //합집합 개수 구하기
    var total = str1.length + str2.length - same;
    
    return Math.floor(same / total * 65536);
}

이번 문제는 TC 4, 7, 9, 10, 11에서 통과를 못 해서 오래 걸렸다.

반례를 찾아 내가 어떤 부분을 놓쳤는지를 확인하고 다시 코드를 고쳤다.

먼저 주어진 문자열 str1과 str2를 다중집합으로 만들기 위해 함수 making을 만들었다.

str1이 "FRANCE"일 때 making 함수를 동작하면 아래와 같이 가공이 된다.

function making(str){
    
    str = str.split("").map((v,i)=>{if(i+1 < str.length) return str[i]+str[i+1]});
    //[ 'FR', 'RA', 'AN', 'NC', 'CE', undefined ]
    
    //undefined 제거
    if(str[str.length-1] == undefined){
        str = str.slice(0, str.length-1);
    }
    //[ 'FR', 'RA', 'AN', 'NC', 'CE' ]
    
    //특문,숫자 포함 요소 제거 + 소문자로 변경
    str = str.filter(v => (/[a-zA-Z]{2}/g).test(v)).map(v=>v.toLowerCase());
    //[ 'fr', 'ra', 'an', 'nc', 'ce' ]
    
    return str;
}

앞 글자와 뒤 글자를 붙일 때 undefined가 자꾸 생성되어 그 부분을 삭제하는 로직을 따로 만들어줬다.

function solution(str1, str2) {

    str1 = making(str1);
    str2 = making(str2);
    
    if(str1.length == 0 && str2.length == 0){
        return 65536;
    }
    
    //교집합 개수 구하기
    var same = 0;
    
    for(var i = 0; i < str1.length; i++){
        for(var j = 0; j < str2.length; j++){
            
            if(str1[i] == str2[j]){
                same++;
                str2[j] = "";
                break;
            }
        }
    }
    //합집합 개수 구하기
    var total = str1.length + str2.length - same;
    
    return Math.floor(same / total * 65536);
}

만약에 str1과 str2의 길이가 0이면 바로 65536을 리턴해준다.

교집합을 구하는 부분에서 원래는 아래의 코드처럼 indexOf로 교집합의 개수를 구했는데 이 부분때문에 몇몇 TC에서 오류가 발생했다.

for(var val of str1){
    if(str2.indexOf(val) > -1){
        same1++;    }}

만약에 STR1이 "aaabbbb"이고 STR2이 "aaaabbb"라면 가공 후 두 집합의 교집합 개수는 5가 된다.

하지만 위의 잘못된 코드로 동작했을 때는 6이 나오는데, 

str1 = [ 'aa', 'aa', 'ab', 'bb', 'bb', 'bb' ], str2 = [ 'aa', 'aa', 'aa', 'ab', 'bb', 'bb' ] 이렇게 있을 때 

str1에 'bb'가 3개있고 str2의 'bb'는 2개가 있는데 교집합 체크 후에도 str2에는 'bb'가 계속 있기에 bb의 교집합이 3개로 나오게 되는 것이다.

해결법으로 동일한 원소가 있다면 교집합 개수(same)을 카운트하고 해당 요소를 빈값으로 만들어줬다.

합집합은 두 집합의 개수 - 교집합 개수로 구하면 된다.

Math.floor로 소수점 자리는 없애고 리턴을 해주면 끝이다.

 

+다른 사람 풀이

function solution (str1, str2) {

  function explode(text) {
    const result = [];
    for (let i = 0; i < text.length - 1; i++) {
      const node = text.substr(i, 2);
      if (node.match(/[A-Za-z]{2}/)) {
        result.push(node.toLowerCase());
      }
    }
    return result;
  }

  const arr1 = explode(str1);
  const arr2 = explode(str2);
  const set = new Set([...arr1, ...arr2]);
  let union = 0;
  let intersection = 0;

  set.forEach(item => {
    const has1 = arr1.filter(x => x === item).length;
    const has2 = arr2.filter(x => x === item).length;
    union += Math.max(has1, has2);
    intersection += Math.min(has1, has2);
  })
  return union === 0 ? 65536 : Math.floor(intersection / union * 65536);
}

const node = text.substr(i, 2);로 undefined를 내지 않고 앞뒤글자를 붙이고 정규식을 통과한 값만 배열에 담아주는 식으로 문자열을 가공했다.

set처리를 하면 Set(8) { 'fr', 'ra', 'an', 'nc', 'ce', 're', 'en', 'ch' }가 된다.

has1, has2 변수에는 일치하는 값의 길이를 담아주고

합집합에는 has1, has2 중 큰 값을, 교집합에는 작은 값을 계속 더해줬다.

교집합 합집합 구하는 부분이 신기하다.