[node.js] 연산자 끼워넣기 ( 백준 14888번 )

// 백준 14888번 연산자 끼워넣기를 풀었습니다.

const readline = require("readline");

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

const permutations = function* (elements) {
    if (elements.length === 1) {
        yield elements;
    } else {
        const [first, ...rest] = elements;

        for (const a of permutations(rest)) {
            for (let i = 0; i < elements.length; i++) {
                const start = a.slice(0, i);
                const ended = a.slice(i);
                yield [...start, first, ...ended];
            }
        }
    }
};

const makeExpression = (numbers, operators) => {
    let operIndex = 0;
    let acc = numbers[0];
    for (let i = 1; i < numbers.length; i++) {
        const b = numbers[i];
        const oper = operators[operIndex++];

        if (oper === "/") {
            acc = parseInt(acc / b);
        } else if (oper === "+") {
            acc = acc + b;
        } else if (oper === "-") {
            acc = acc - b;
        } else {
            acc = acc * b;
        }
    }

    return acc;
};

const input = [];

rl.on("line", (line) => {
    input.push(line);
}).on("close", () => {
    const numbers = [];
    const operators = [];

    input.slice(1).forEach((line, i) => {
        if (i === 0) {
            numbers.push(...line.split(" ").map(Number));
        } else {
            const obj = {};
            line.split(" ").map((el, i) => {
                const operator = ["+", "-", "*", "/"][i];
                obj[operator] = el;
            });
            Object.entries(obj).forEach((el) => {
                for (let i = 0; i < el[1]; i++) {
                    operators.push(el[0]);
                }
            });
        }
    });

    let maxValue = -987654321;
    let minValue = 987654321;
    for (const operSet of permutations(operators)) {
        const value = makeExpression(numbers, operSet);
        maxValue = Math.max(maxValue, value);
        minValue = Math.min(minValue, value);
    }

    if (maxValue == "-0" || maxValue == "+0") maxValue = 0;
    if (minValue == "-0" || minValue == "+0") minValue = 0;

    console.log(maxValue);
    console.log(minValue);
});

// 이 문제를 풀면서 유의해야 했던 사항
// 문제를 잘못 읽어서 숫자도 순열로 고친 점
// 자바스크립트의 나누기로 인해서 원래의 수식 방법을 쓸 수 없던 점
// new Function()을 이용한 수식이 생각보다 느린 점
// 자바스크립트에 0이 +0과 -0으로 두 개가 존재하는 점

주석으로도 적어놨는데, 이 문제를 푸는 데 상당히 시간이 걸렸고, 이유는 주석과 같다.

첫째로, 문제를 잘못 읽었다.
연산자 순열을 구할 때, 숫자도 섞일 수 있다고 생각했다. 풀면서도, 이러면 사실 상 4중 for문인데 그래도 되나 싶었건만...
아무리 봐도 이상해 다시 문제를 읽고 내가 오독했음을 알았다.
둘째로, new Function(expression)의 형태를 취한 점이 문제였다.
하나의 수식으로 만들어서 계산하려다 보니 문제에, 연산자의 우선순위를 고려하지 않는다는 점을 몰랐고,
또 막상 그렇게 하고 나니 자바스크립트의 나누기가 double 형이라는 것을 고려하지 못했다.

또, 이 부분을 모두 고치고 난 다음에도 문제였는데 ( 정상적으로 풀었음에도 시간초과가 발생했다. )
new Function()이 eval()보다 안전하고 빠르다고 들었기에 사용했음에도, 이게 그냥 수식보다 100배(!?)에 가까운 시간 차이가 났다.
그래서 결국 if문으로 4가지 연산을 모두 처리하게끔 고쳤다.

마지막으로 자바스크립트는 0을, +0과 -0으로 표시한다는 점이었다.
이건 또 의식하지도 못한 문제인데, 이로 인해서 35% 지점에서 오답이 나왔다.

그 외에는 별 거 없는 순열 문제였다.