(javascript) 사칙연산

코딩테스트 연습 - 사칙연산 | 프로그래머스 스쿨

프로그래머스

 

 재귀적으로 풀 수 있다.

 예시의 문자열 1 - 3 + 5 - 8을 (1 - 3) + (5 - 8)과 같은 형태로 나타내보면, 가운데에 있는 + 연산자를 기준으로 (1 - 3)과 (5 - 8)이 각각 문제에서 제시하는 형태가 되는 것을 알 수 있다.

 주어진 문제를 푸는 함수를 foo라고 하면, foo( "1 - 3 + 5 - 8")은 foo("1 - 3") + foo("5 - 8")이 되는 것이다.

 

 문제는 주어진 문자열에서 각 연산자마다 재귀한다.

 예를 들어, 1 - 3 + 5 - 8의 경우, 먼저 (1) - (3 + 5 - 8)로 나누고, 그 다음은 (1 - 3) + (5 - 8)로 나누고, 마지막으로 (1 - 3 + 5) - (8)로 나눈다.

 (1) - (3 + 5 - 8)의 경우, 전체 결과의 최대값을 구하려면 -연산자의 왼쪽은 최대값, -연산자의 오른쪽은 최소값을 가져야 한다.

 (1)은 더이상 나눌 수 없으니 최소값과 최대값을 그냥 1로 둔다. (3 + 5 - 8)은 다시 재귀해서 (3) + (5 - 8)과 (3 + 5) - (8)로 나눈다.

 이런 방법으로 가능한 모든 괄호 조합에서 전체 배열의 최대값을 구할 수 있다.

 

 그러나 그냥 최대값을 구하는것만으로는 효율성 테스트를 통과할 수 없다.

 문제의 카테고리를 보면 동적 계획법(DP)로 되어있다.

 즉, 중간 결과를 저장하는 과정이 필요하다.

 (1) - (3 + 5 - 8)에서도, (1 - 3) + (5 - 8)에서도, 중간에 (5 - 8)을 계산해야한다

 중복된 계산을 줄이기 위해 map 형태로 중간 결과를 저장했다.

 

코드

 

function solution(arr) {
    var answer = -1;

    const memo = new Map();

    const dfs = (start, end) => {
        const key = `${start}, ${end}`;
        if (memo.has(key)) return memo.get(key);
        if (start === end) {
            var v = +arr[start];
            return { min: v, max: v };
        }
        var min_val = Infinity, max_val = -Infinity;
        for (var i = start + 1; i < end; i += 2) {
            var op = arr[i];
            var { min: left_min, max: left_max } = dfs(start, i - 1);
            var { min: right_min, max: right_max } = dfs(i + 1, end);

            for (var l of [left_min, left_max]) {
                for (var r of [right_min, right_max]) {
                    let temp;
                    if (op === '+') {
                        temp = l + r;
                    } else if (op === '-') {
                        temp = l - r;
                    }
                    if (temp < min_val) min_val = temp;
                    if (temp > max_val) max_val = temp;
                }
            }
        }
        memo.set(key, { min: min_val, max: max_val });
        return { min: min_val, max: max_val };
    }

    var answer = dfs(0, arr.length - 1).max;
    return answer;
}

 

결과