[프로그래머스/JavaScript] Lv.2 수식 최대화

 

재귀 함수를 통해 답을 도출

 

 

프로그래머스

 

 

문제 풀이

사용 가능한 연산자를 반복하는  DFS 함수, 수식에 해당 연산자를 포함하고 있는 값들을 계산하는 재귀 함수를 사용하여 해당 문제를 풀었다.

let answer = [];
function solution(expression) {
    // 1) 사용 가능한 연산자를 배열에 담는다.
    const opts = ["+", "-", "*"];

    // 2) 문자열을 연산자를 구분으로 배열로 변환한다. 해당 배열은 구분 연산자 또한 포함한다.
    let cal = expression.split(/(\D)/);
   
    /* 
      3) opts 배열(연산자 배열)을 대상으로 DFS 함수 생성
       - opts : 연산자 배열
       - cal : 계산할 수식이 담긴 배열
    */
    dfs(opts, cal)
    
    // 4) 결과 값이 담긴 answer 배열의 최대 값을 return 한다.
    return Math.max(...answer);
};
function dfs(opts, cal){
    /* 
    5) 사용 가능한 연산자가 없다면 cal 배열에 결과 값만 담겨있다.
       결과 값 return 한다. (음수를 양수로 변경)
    */
    if(opts.length === 0) return answer.push(Math.abs(cal));
    
    
    // 6) cal 배열(수식 배열)을 대상으로 DFS 함수  calculation(opt, cal) 생성
    opts.forEach((opt, i) => {
        
        // 7) 변경되는 opts(연산자 배열), cal(수식 배열) 담고 DFS 재귀함수 실행
        dfs([...opts.slice(0, i), ...opts.slice(i+1)], calculation(opt, cal));
    });

    return answer;
}
// 7) 수식에서 해당 sign(연산자)가 포함된 값을 계산하는 DFS함수
function calculation(sign, cal){
    // 8) 연산자가 포함되지 않으면 남은 수식을 return 한다.
    if(!cal.includes(sign)) return cal;
    
    // 9) 연산자가 포함된 index를 구한다.
    let idx = cal.indexOf(sign);
    
    // 10) 수식에서 해당 연산자를 계산한다.
    let sum = cal[idx-1] + sign + cal[idx+1];
    
    // 11) 변경되는 수식을 담고 DFS  재귀함수 실행
    cal = calculation(sign, [...cal.slice(0, idx-1), eval(sum), ...cal.slice(idx+2)]);

    // 12) 남은 수식을 return 한다.
    return cal;
}