16637번 - 괄호 추가하기

1️⃣ 구현

 

✏️ 풀이 과정

많이 복잡해 보이지만 연산자를 기준으로 보면 최대 9개(N이 19일 경우 연산자는 9개) 중에서 먼저 계산할 것을 고르는 문제와 같습니다. 괄호 중첩이 안되기 때문에 실제로는 수가 더 적으나 경우의 수가 2^9보다 작다는 데서 모든 경우의 수를 따져야 하는 문제임을 알 수 있습니다.

 

남은 것은 모든 경우를 테스트할 수 있도록 계산 과정을 모델링하는 것인데 이런 구현 문제에서는 항상 적극적으로 모듈화를 이용하는 것이 좋습니다. 아래코드의 경우 경우의 수를 만드는 모듈, 경우의 수로 max값을 업데이트하는 모듈, 넘긴 두 수와 연산자로 연산을 실행하는 모듈까지 총 3개의 모듈을 만들어서 로직을 구현했습니다.

 

여기서 핵심이 되는 부분은 경우의 수를 만드는 로직인데 스택을 이용해서 make 함수에서 특정 연산자를 먼저 계산할 경우 스택에서 수 하나를 꺼내 계산하고 결과물을 다시 스택에 넣는 방식으로 최종적인 계산 식을 저장하고 update 함수에서 이 스택을 순회하면서 계산 결과를 얻고 max값을 업데이트하는 방법을 사용했습니다.

 

구체적으로는 처음에 수 하나를 넣고 이후부터 for문을 이용해서 연산자와 수를 하나씩 넣으면서 스택을 채우다가 중복순열을 통해 만든 비트마스킹 수(true, false 대신 사용)에서 우선적으로 계산할 연산자임을 가리키면 스택에서 수를 하나 꺼내서 연산을 하고 넣으면 스택에는 왼쪽부터 순서대로 계산하면 완성되는 식이 남게 됩니다.

 

주의할 점은 연산자와 수를 한 단위로 갖고가야하기 때문에 for문을 2칸씩 뛰어야 합니다. 로그를 찍어보면서 조절하면 정확한 인덱스 범위를 설정할 수 있습니다. 또한 중첩 괄호를 피하기 위해 직전에 괄호가 생긴 경우에는 바로 다음 번에 괄호가 나오지 않도록 if문으로 처리해야 합니다.

 

⏱ 시간 복잡도

다른 함수는 모두 일차원 배열을 순회하기 때문에 O(N)이지만 중복순열 함수의 경우는 O(2^N)이 됩니다. 각 순열에 대해 make와 update를 실행하기 때문에 전체 시간복잡도는 O(N * 2^N)이 됩니다. N이 최대 19인데 실제로는 연산자 수에 해당하는 절반 이하가 적용되기 때문에 19 * 2^9 = 9728 미만의 계산으로 문제를 해결할 수 있습니다.  

 

💻 코드

JavaScript

const input = require("fs")
    .readFileSync(process.platform === "linux" ? "/dev/stdin" : "input.txt")
    .toString()
    .trim()
    .split("\n");

const N = Number(input[0]);
const len = Math.floor(N / 2);
let max = -Infinity;

const arr = input[1].split("").map((item, index) => {
    if (index % 2 == 0) {
        return Number(item);
    } else {
        return item;
    }
});

const calculate = (oper, a, b) => {
    if (oper === "+") {
        return a + b;
    } else if (oper === "-") {
        return a - b;
    } else {
        return a * b;
    }
};

const make = (stack, bit) => {
    for (let i = 1; i < N - 1; i += 2) {
        if ((bit & (1 << Math.floor(i / 2))) === 0) {
            stack.push(arr[i]);
            stack.push(arr[i + 1]);
        } else {
            stack.push(calculate(arr[i], stack.pop(), arr[i + 1]));
        }
    }
};

const update = (stack) => {
    let num = stack[0];
    for (let i = 1; i < stack.length - 1; i += 2) {
        num = calculate(stack[i], num, stack[i + 1]);
    }
    if (num > max) {
        max = num;
    }
};

const r_perm = (n, bit) => {
    if (n === len) {
        let stack = [];
        stack.push(arr[0]);
        make(stack, bit);
        update(stack);
        return;
    }
    r_perm(n + 1, bit);
    if ((bit & (1 << (n - 1))) === 0) {
        r_perm(n + 1, bit | (1 << n));
    }
};

r_perm(0, 0);
console.log(max);