[Algorithm/JS] 백준 1541번 잃어버린 괄호

🔗 문제 바로가기 (opens new window)

Question

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.

그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.

괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

Input

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.

Output

첫째 줄에 정답을 출력한다.

Example

Input 1

첫째 줄에 정답을 출력한다.

Output 1

-35

Input 2

10+20+30+40

Output 2

100

Input 3

00009-00009

Output 3

0

Solution

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : '../input.txt';
const input = fs.readFileSync(filePath).toString().trim();

let block = [];
input.split('-').map((item) => {
  let sum = 0;
  let num = item.split('+').map(Number);
  num.forEach((n) => (sum += n));
  block.push(sum);
});

let total = block[0];
for (let i = 1; i < block.length; i++) {
  total -= block[i];
}

console.log(total);

알고리즘: 그리디

적절히 괄호를 쳐서 최소합을 만드는 방법은 마이너스(-)를 기준으로 쪼개었을 때(분할된 부분들을 블럭이라고 하겠다.) 이 블럭내에서 더하기(+) 연산이 있다면 수행하고, 수행한 블럭들 끼리 빼기 연산을 하면 최솟값이 된다.

예를들어 55-50+40 를 입력받을 경우

1 . 빼기(-) 연산을 기준으로 나눈다. ( [ ] 는 블럭을 표기함.)

[ 55 ] [50+40]

2. 블럭 내 더하기(+) 연산을 수행한다.

[ 55 ] [ 90 ]

3. 더하기(+) 연산까지 완료한 후 블럭들 끼리 뺀다.

55 - 90 = -35

이처럼 55-50+40 에 적절히 괄호를 쳤을 때 나올 수 있는 최솟값은 -35가 된다.

let block = [];
input.split('-').map((item) => {
  let sum = 0;
  let num = item.split('+').map(Number);
  num.forEach((n) => (sum += n));
  block.push(sum);
});

위 코드는 빼기(-)를 기준으로 split 함수로 쪼갠 후 map 함수를 사용해 블럭 내 더하기(+)연산을 실행한 값을 block 이라는 배열 변수에 push 했다. 여기까지 수행하면 위 예시에서 2번까지 진행된 것이.

let total = block[0];
for (let i = 1; i < block.length; i++) {
  total -= block[i];
}

console.log(total);

위 코드는 각 블럭의 빼기(-) 수행하는 코드이다.

total 변수를 첫번째 블럭의 값으로 초기화한 후 block 의 길이만 큼 반복문을 수행해 최종적인 최솟값을 도출했다.

성공!