[BOJ/JavaScript] 1541: 잃어버린 괄호

문제

이 식에 괄호를 적절하게 쳐서 식의 값을 최소로 만드려고 한다.

식은 0~9, +, -로만 이루어져 있다. 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다.

 

풀이

그리디 알고리즘을 연습하고자 푼 문제다. 하지만 아이디어가 잘 떠오르지 않았다. 힌트를 얻어 풀 수 있었다. 아직 JS에 익숙하지 않아 파싱하는 데 어려움을 겪었다. 그리디 알고리즘은 아이디만 떠오르면 푸는 건 금방인데 아이디어가 잘 안떠오르면 시간이 많이 걸리는 듯하다..

💡 숫자로 판별될 수 있는 값과 그렇지 않은 값이 배열에 혼재되어 있으면 `map(Number)`를 사용할 수 없음에 주의하자.

 

최소값을 만드려면 뺄셈이 시작되면 무조건 많은 수를 빼야 한다. 이를 위해, `-`를 기준으로 문자열을 파싱한다. 파싱한 첫 식을 제외하고 나머지 식을 모두 빼주면 식의 값이 최소를 만족한다.

 

ex) `10+20+30-40+50-60+70`라는 식에서 `-`를 기준으로 파싱하면 `10+20+30`, `40+50+60+70`으로 나뉜다. 첫 번째 식을 제외하고 모든 식을 빼주면 최적의 값을 보장한다.

 

코드

처음 작성한 코드다. 코드가 다소 중복이 많은 점이 아쉽다.

const input = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt", "utf8")
  .trim();

const numbers = input.replaceAll("-", " ").split(" ");

let sum = 0;
for (let i = 0; i < numbers.length; i++) {
  if (i === 0) {
    numbers[i] = numbers[i]
      .split("+")
      .map(Number)
      .reduce((acc, num) => (acc += num), 0);
    sum += numbers[i];
    continue;
  }
  numbers[i] = numbers[i]
    .split("+")
    .map(Number)
    .reduce((acc, num) => (acc += num), 0);
  sum -= Number(numbers[i]);
}

console.log(sum);

함수형 프로그래밍 방식으로 변환한 코드다.

const input = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt", "utf8")
  .trim();

const blocks = input.split("-");

const sum = blocks
  .map(block =>
    block.split("+").map(Number).reduce((acc, val) => acc + val, 0)
  )
  .reduce((acc, val, idx) => (idx === 0 ? val : acc - val));

console.log(sum);