[JS/Programmers] 67257. [카카오 인턴] 수식 최대화

💬 문제

문제 난이도: Programmers Lv.2

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/67257

❗️접근방법

완전 탐색, 순열, 문자열 파싱

👆 1차 코드

function makePriority(arr){
    const result = [];
    if (arr.length === 1) {
        result.push([arr[0]]);
    }
    else if(arr.length === 2){
        result.push([arr[0], arr[1]]);
        result.push([arr[1], arr[0]]);
    }else{
        result.push(['-', '+', '*']);
        result.push(['-', '*', '+']);
        result.push(['+', '*', '-']);
        result.push(['+', '-', '*']);
        result.push(['*', '+', '-']);
        result.push(['*', '-', '+']);
    }
    return result;
}

function solution(expression) {
    let answer = 0;
    const arr = [];
    const set = new Set();
    let num = ''
    for (let i = 0; i < expression.length; i+=1){
        if(isNaN(expression[i])){
            arr.push(parseInt(num));
            num = '';
            arr.push(expression[i]);
            set.add(expression[i]);
        }else num += expression[i];
    }
    arr.push(parseInt(num))
    const priorities = makePriority(Array.from(set));
    for (let i = 0; i < priorities.length; i+=1){
        const copy = [...arr];
        const pArr = priorities[i];
        while (pArr.length > 0){
            const op = pArr.pop();
            let idx =  copy.findIndex(elem => elem === op);
            while (idx >= 0){
                let temp = 0;
                if (op === '*') temp= copy[idx-1] * copy[idx+1];
                else if(op === '-')temp= copy[idx-1] - copy[idx+1];
                else temp= copy[idx-1] + copy[idx+1];
                copy.splice(idx-1, 3, temp);
                idx = copy.findIndex(elem => elem === op);
            }
        }
        if(Math.abs(copy[0]) >= answer) answer = Math.abs(copy[0]);
    }
    return answer;
}

✌️ 2차 코드(기능단위로 분리 + dfs 사용해 순열 생성)

function makePermutation(arr){
    const N = arr.length; 
    const result = []
    function dfs(tmp, visited){
        if(tmp.length === N) return result.push(tmp);
        for (let i = 0; i < N; i+=1){
            if (!visited[i]) {
                visited[i] = 1;
                dfs(tmp.concat([arr[i]]), visited);
                visited[i] = 0;
            }
        }
    }
    
    for (let i = 0; i < N; i+=1){
        const visited = new Array(N).fill(0);
        visited[i] = 1
        dfs([arr[i]], visited);
    }    
    return result;
}

function getResult(priority, arr){
    while(priority.length > 0){
        const op = priority.pop();
        let idx = arr.findIndex(elem=>elem === op);
        let tmp = 0;
        while(idx >= 0){
            if (op === '+') tmp = arr[idx-1] + arr[idx+1];
            else if (op === '-') tmp = arr[idx-1] - arr[idx+1];
            else tmp = arr[idx-1] * arr[idx+1];
            
            arr.splice(idx-1, 3, tmp);
            idx = arr.findIndex(elem=>elem === op);
        }
    }
    return Math.abs(arr[0]);
}

function solution(expression){
    const set = new Set();
    const arr = [];
    let num = '';
    for (let i = 0; i < expression.length; i+=1){
        if (isNaN(expression[i])) {
            arr.push(parseInt(num));
            arr.push(expression[i]);
            set.add(expression[i]);
						num = '';
        }else num += expression[i];
    }
    arr.push(parseInt(num));
    
    const permutations = makePermutation(Array.from(set));

    let answer = -1;
    for (let i = 0; i < permutations.length; i+=1){
        const copy = [...arr];
        const tmp = getResult(permutations[i], copy);
        if (tmp > answer) answer = tmp;
    }
    return answer;
    
}

✍️ 이 문제에서 사용된 메서드 정리

Array.prototype.concat()
인자로 주어진 배열이나 값들을 기존 배열에 합쳐서 새 배열을 반환

(참고: https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/concat)

Array.prototype.splice()
배열의 기존 요소를 삭제 또는 교체하거나 새 요소를 추가하여 배열의 내용을 변경
-> 새로운 배열 만들지 않음.

arr.splice(index-1, 3, tmp);
// arr에서 index-1번째 원소부터 3개의 원소를 지우고 그 자리에 tmp 라는 값을 추가

(참고: https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/splice)