[21/09/09] 뉴스클러스터링 거리두기 수식최대화

rat8397·2021년 9월 9일
0

코드카타

목록 보기
26/44
post-thumbnail

뉴스 클러스터링

풀이1

function makeDajung(str){
    const result = []
    for(let i=0;i<str.length-1;i++){
        const target = str.slice(i,i+2).match(/([a-zA-Z])/gi);
        if(target && target.length === 2){
            result.push(target.join(""))
        }       
    }
    return result;
}
function getIntersectionNum(first,second){
    let result = [];
    [...new Set(first)].forEach((element)=>{
        if(second.includes(element)){
            // is Intersection Element
            const firstEl = first.filter((temp)=>temp === element)
            const secondEl = second.filter((temp)=>temp === element)
            
            if(firstEl.length < secondEl.length){
                result = result.concat(firstEl);
            }else{
                result = result.concat(secondEl);
            }
        }
    })
    return result;
}
function getUnionNum(first,second){
    let result = [];
    const firstSet = [...new Set(first)];
    const secondSet = [...new Set(second)]
    firstSet.forEach((element)=>{
        if(second.includes(element)){
            const firstEl = first.filter((temp)=>temp === element)
            const secondEl = second.filter((temp)=>temp === element)
            
            if(firstEl.length < secondEl.length){
                result = result.concat(secondEl);
            }else{
                result = result.concat(firstEl);
            }
        }else{
            const firstEl = first.filter(temp=>temp===element);
            result = result.concat(firstEl);
        }
    })
    
    secondSet.forEach((element)=>{
        if(first.includes(element)){
            // isIntersect
        }else{
            const secondEl = second.filter(temp=>temp===element);
            result = result.concat(secondEl);
        }
    })
    return result;
}
function solution(str1,str2){
    // 다중집합을 구하고
    const first = makeDajung(str1.toLowerCase());
    const second = makeDajung(str2.toLowerCase());
    
    // 둘다 공집합이면 65536
    if(first.length === 0 && second.length === 0){
        return 65536;
    }
  	// 다중집합들의 교집합과 합집합을 구한다.
    const inter = getIntersectionNum(first,second);
    const union = getUnionNum(first,second);
    
    return Math.floor((inter.length/union.length) * 65536)
    
}

풀이2

풀이1의 방식엔 너무 불필요한 코드가 많아 삭제하고 다음과 같이 리팩토링하였다.

function makeDajung(str){
    const result = [];
    for(let i=0;i<str.length-1;i++){
        const tar = str.slice(i,i+2).match(/[a-zA-Z]/gi);
        
        if(tar && tar.length === 2) result.push(tar.join(""));
    }
    return result;
}
function getInterUnionNum(bothAB,A,B,onlyA,onlyB){
    let gyo = []
    let hap = []
    bothAB.forEach(el => {
        const interA = A.filter(ael => ael === el);    
        const interB = B.filter(bel => bel === el);
        
        if(interA.length < interB.length){
            gyo = gyo.concat(interA);
            hap = hap.concat(interB);
        }else{
            gyo = gyo.concat(interB);
            hap = hap.concat(interA);
        }
    
    })
    return [gyo,[...onlyA,...hap,...onlyB]]
}
function solution(str1,str2){
    // 자신만의 원소 - 공통원소를 구하면 더 쉽게할 수 있을것같다.
    const A = makeDajung(str1.toLowerCase());
    const B = makeDajung(str2.toLowerCase());
    
    if(A.length === 0 && B.length === 0) return 65536;
    
    // 자신만의 원소와 공통 원소들을 구한다. 이 때 자신만의 원소는 중복이 되어서는 안됨. 공통 원소는 이들을 순회하며 각 집합에 몇개씩있는지 판별해야하므로 중복을 제거해주어야 더 수월하다.
    const onlyA = A.filter(el=>!B.includes(el)) 
    const onlyB = B.filter(el=>!A.includes(el)) 
    const bothAB = [...new Set(A.filter(el=>B.includes(el)))]
    
    
    // 교집합과 합집합을 구했으므로
    const [inter,union] = getInterUnionNum(bothAB,A,B,onlyA,onlyB);
    
    // 자카드 유사도 도출가능
    return Math.floor((inter.length/union.length)*65536)
          
    
}
  • 설명은 주석에 있다.

풀이3

굳이 교집합 합집합을 구할 필요는 없다. 우리는 갯수만 알면 되므로 다음과 같이 풀수도있다.

function solution(str1,str2){
    const A = makeDajung(str1.toLowerCase());
    const B = makeDajung(str2.toLowerCase());
    
    if(A.length === 0 && B.length === 0) return 65536;
    
    let inter = 0;
    let union = 0;
    const AB = [...new Set([...A,...B])];
    AB.forEach(el=>{
        // 중복이 제거된 모든 요소 집합을 돈다.
        const a = A.filter(ael => ael === el).length;
        const b = B.filter(bel => bel === el).length;
      
       
        
        if(a===0 || b===0){
            // 한쪽에만 포함된 요소이므로 union에 값을 더해준다.
            union += a + b;
        }else{
            // 양쪽에 포함된 요소이므로 다중집합의 교집합 합집합의미에 맞게 값을 더해준다.
            inter += Math.min(a,b);
            union += Math.max(a,b);
        }
        
    })
    
    return Math.floor((inter/union) * 65536)

    
}

거리두기

  • 참고 사진 1
function isValidate(place){
  // 맨해튼 거리가 1인 경우
    const mht_1_x = [0,0,-1,1]
    const mht_1_y = [-1,1,0,0]
  // 맨해튼 거리가 2인 경우
    const mht_2_x = [0,2,-2,0,-1,1,1,-1]
    const mht_2_y = [2,0,0,-2,-1,1,-1,1]
    for(let i=0;i<place.length;i++){
        for(let j=0;j<place[i].length;j++){
            if(place[i][j] === 'P'){
                // 사람이 등장하면 맨해튼거리1 , 맨해튼거리2 위치에 사람이 있는지를 점검한다.
              
                // 맨해튼 거리 1인 경우
                for(let k=0;k<mht_1_x.length;k++){
                    const cx = i+mht_1_x[k];
                    const cy = j+mht_1_y[k];
                    // 1인 경우에 사람이 있으면 무조건 false 이다.
                    if(place[cx] && place[cx][cy] && place[cx][cy] === 'P') return false;
                }
                // 맨해튼 거리 2인 경우
                for(let k=0;k<mht_2_x.length;k++){
                    const cx = i+mht_2_x[k];
                    const cy = j+mht_2_y[k];
                    
                    // 2인 자리에 사람이 있다면 ?
                    if(place[cx] && place[cx][cy] === 'P'){
                        
                        // 로우가 같다면 사이에 좌석이 비었는지를 점검 -> 비어있으면 false;
                        if(cx === i ){
                            if(cy > j && place[cx][cy - 1] === 'O'){
                                return false;
                            }
                            
                            if(cy < j && place[cx][cy + 1] === 'O' ){
                                return false;
                            }
                            
                        }
                      
                        // 컬럼이 같다면 사이에 좌석이 비었는지를 점검 -> 비어있으면 false;
                        if(cy === j){
                            if(cx > i && place[cx-1][cy] === 'O') return false;
                         
                            if(cx < i && place[cx+1][cy] === 'O') return false;
                        }
                        
                        if(cx !== i && cy !== j){
                        // 로우와 컬럼 모두 다른 경우는 대각의 경우이다.
                        // 대각의 경우 참고사진 1과 같은지를 점검한다.
                            if(place[i+mht_2_x[k]][j] === 'O' || place[i][j+mht_2_y[k]] === 'O') return false;
                        }
                        
                    }
                }
                
                
                
            }
        }
    }
  
    위 과정이 모두 통과되면 true
    return true;
}
function solution(places){
    return places.map(place => {
        // 대기실
        
        return isValidate(place) ? 1 : 0;
    })
    
}

수식최대화

풀이1 using array

const priorityCase = ["*-+","*+-","+*-","+-*","-+*","+-*"]
function compute(first,second,exp){
    if(exp === '*'){
        return `${+first * +second}`;
    }
    
    if(exp === '-'){
        return `${+first - +second}`;
    }
    
    if(exp === '+'){
        return `${+first + +second}`;
    }
}
function getPrize(exp,pri){
    
    pri.forEach(op=>{
        for(let i = 0;i<exp.length;i++){
            
            if(exp[i] === op){
                const value = compute(exp[i-1],exp[i+1],exp[i]);
                
                exp.splice(i-1,3,value);               
                i = i - 1;
            }
            
        }
    })
    
    return Math.abs(+exp[0]);
}
function solution(expression){
    let answer = 0;
    
    const exp = expression.split(/([-*+])/gi)
    
    priorityCase.forEach(priority=>{
        const result = getPrize([...exp],priority.split(""));
        
        answer = Math.max(answer,result);
        
    })
    return answer;
}

풀이2 using stack

const priorityCase = ["*-+","*+-","+*-","+-*","-+*","+-*"]
function compute(first,second,exp){
    if(exp === '*'){
        return `${+first * +second}`;
    }
    
    if(exp === '-'){
        return `${+first - +second}`;
    }
    
    if(exp === '+'){
        return `${+first + +second}`;
    }
}
function getPrize(exp,pri){

    pri.forEach(op=>{
        const stack = [];
        let i = 0;
        while(i<exp.length){
            if(exp[i] === op){
                stack.push(compute(stack.pop(),exp[i+1],op));
                i = i + 2;
            }else{
                stack.push(exp[i]);
                i = i + 1;
            }
        }
      // 스택에 넣어놓은 걸 다음에 순회한다.
        exp = [...stack];
    })
    return Math.abs(+exp[0]);
    
            
   
}
function solution(expression){
    let answer = 0;
    
    const exp = expression.split(/([-*+])/gi)
    
    priorityCase.forEach(priority=>{
        const result = getPrize([...exp],priority.split(""));
        
        answer = Math.max(answer,result);
        
    })
    return answer;
}
profile
Frontend Ninja

0개의 댓글