[백준 1541] 잃어버린 괄호 with Node.js

문제 링크

https://www.acmicpc.net/problem/1541

1541번: 잃어버린 괄호

풀이

const solve = expression => {
  const getSum = arr => {
    return arr.split(/[\+-]/).map(v => +v).reduce((acc, n) => acc + n, 0);
  }
  const firstMinus = expression.indexOf('-');
  if (firstMinus === -1) {
    console.log(getSum(expression));
  } else {
    const plus = getSum(expression.slice(0, firstMinus));
    const minus = getSum(expression.slice(firstMinus+1));
    console.log(plus - minus);
  }
};

const expression = require('fs').readFileSync('/dev/stdin').toString().trim();
solve(expression);

식의 값을 최소로 만들기 위해서는 뺄셈 연산자 뒤의 수를 최대한 크게 만들면 된다.

예를 들어, 25-40+30-55 라는 식이 있으면, 25-(40+30)-55로 만들면 된다.

이 때, 괄호는 첫 번째 뺄셈 연산자 바로 직후에 열고, 그 다음 뺄셈 연산자 바로 직전에 닫는다.

이렇게하면 최종적으로 식은 25-40-30-55가 된다.

 

식이 길어지더라도 이런식으로 계속 괄호를 삽입한다면 결국 첫 번째 뺄셈 연산자 이후의 모든 수는 음수가 된다.

(첫 번째 뺄셈 연산자 직전까지 나온 모든 수의 합 - 그 다음 수 - 그 다음 수 - 그 다음 수 - 그 다음 수 ...)

따라서, 첫 번째 뺄셈 연산자 전까지의 수의 합에서 그 이후에 등장하는 모든 수의 합을 뺀 값이 식의 최솟값이 된다.

 

주어진 문자열을 첫 번째 뺄셈 연산자를 기준으로 좌우로 나눈 후,

+ 또는 - 를 기준으로  split한 뒤 수들의 합을 구하고, 그 차를 출력한다.

만약 뺄셈 연산자가 하나도 없다면 모든 수를 더하여 출력한다.