[21/10/28-29 KATA NINJA] BFS DFS Stack Queue 복습

코테 전이라 간단하게 개념 복습을 하려고한다

Minimum Depth of Binary Tree

마지막 리프까지 가는 최단 경로를 구하면된다. 모든 노드를 점검하는 DFS가 아닌, BFS가 적합하다.

var minDepth = function(root) {
    if(!root){
        return 0;
    }
    const queue = []
    
    queue.push([root,1]);
    
    while(queue.length !== 0){
        const [node,depth] = queue.shift();
        
        if(node.left === null && node.right===null){
            return depth;
        }
        
        if(node.left)
        queue.push([node.left,depth+1]);
        if(node.right)
        queue.push([node.right,depth+1]);
        
    }
};

수식최대화

전형적인 스택 문제

const useon = [['*','-','+'],['*','+','-'],['+','*','-'],['+','-','*'],['-','*','+'],['-','+','*']]
function solution(expression) {
    var answer = 0;
    
    const exp = expression.split(/([/+-/*])/gi)
    
    useon.forEach(pri =>{
        let cur = exp;
        let stack = []
        
        
        pri.forEach(operation=>{
            stack = [];
            for(let i=0;i<cur.length;i++){
                if(operation === cur[i]){
                    const first = stack.pop();
                    const second = cur[i+1];
                    const res = getComputed(first,second,operation)
                    stack.push(`${res}`);
                    i++;
                }else{
                    stack.push(cur[i])
                }
            }    
            cur = stack;
        })
        
        const [res] = stack;
        answer = Math.max(answer,Math.abs(+res));
    })    
    
    
    
    return answer;
    
    function getComputed(first,second,operation){
        
        if(operation === '*'){
            return +first * +second
        }
        if(operation === '-'){
            return +first - +second;
        }
        if(operation === '+'){
            return +first + +second;
        }
    }
}

기능개발

function solution(progresses, speeds) {
    var answer = [];
    
    
    while(progresses.length > 0){
        let count = 0;
        
        for(let i=0;i<speeds.length;i++){
            progresses[i] += speeds[i];
        }
        
        while(progresses[0] >= 100){
            progresses.shift();
            speeds.shift();
            count++;
        }
        if(count > 0){
            answer.push(count);
        }
        
    }
    
    return answer;
}

프린터

function solution(priorities, location) {
    let answer = 0;
    
    priorities = priorities.map((item,idx)=>({item,result : location === idx}));
    
    while(priorities.length > 0){
        const {item,result} = priorities.shift();
        
        if(priorities.some(({item:tItem})=>tItem > item)){
            priorities.push({item,result});
            continue;
        }
        
        if(result){
            return answer+1;
        }
        
        answer++;        
        
        
        
        
    }
    
    
}