[백준] 1541. 잃어버린 괄호 (자바스크립트/javascript/node.js/그리디 알고리즘)

 

 

문제를 풀기 위한 아이디어

어려운 문제는 아니다. 그러나 제출했을 때 오류가 나서 다른 방법을 찾느라 좀 번거로웠던 문제이다.

일단 근본적으로 문제를 해결하는 방법은, 최솟값이 나오기 위해서는 마이너스를 최대한 크게 해서 빼는 것이 최솟값이 되기 때문에, 마이너스가 나타나면 마이너스 뒤에서 괄호 "("로 묶기 시작하여 또 다른 마이너스를 만나기 직전에 ")"를 추가하는 방법이다.

예제의 경우 55-50+40 이라면 55-(50+40) 이렇게 하는 것이다.

그렇게 하여 주어진 식을 배열로 다 나누어서 마이너스가 나타나면 "-("로 바꾸고 이런식으로 푼 다음에 마지막에 문자열로 합치고 eval을 이용해서 식을 계산했는데 처음에 런타임에러(SyntaxError)가 나와서 eval은 아무래도 좋은 방법이 아닌 것 같다고 판단되었다.

또한 문제를 읽어보면 수는 0부터 시작할 수 있다고 했으므로 eval("055")를 하게 되면 우리가 기대한 값인 55가 나오지 않고 45가 나오는 것을 알 수가 있다. 값이 달라지므로 위에서 eval 함수말고 다른 방법을 생각했다.

 

우선 주어진 식을 처음에 "-" 기준으로 자른 다음, 그 안에서는 또 "+" 기준으로 자른다. 그리고 "+"기준으로 자른 배열들을 한번씩 돌면서 주어진 수 들을 Number로 바꾸어주고 다 더한다. (Number("055")는 55가 된다.) 그리고 그 값들을 빼주면 된다.

 

예를 들어 055-050+040의 경우 맨 처음 "-" 기준으로 자르면 ["055", "050+040"]이 된다.

그리고 그 각각의 요소들을 또 "+" 기준으로 잘라주는 것이다. 그러면 [["055"], ["050", "040"]]이 되는데, 이 때 각각의 값들을 Number를 이용해서 바꾸어주면 [[55], [50, 40]]이 되고, 각각을 더하면 [55, 90]이 된다. 그리고 처음 값인 55를 제외하고 중간에는 55 - 90 이렇게 빼주면 -35가 나온다.

 

 

내가 작성한 코드 (자바스크립트)

let fs = require("fs");
let expression = fs.readFileSync("/dev/stdin").toString().trim().split("-");
const N = expression.length;
let answer = 0;
let sum = 0;
for (let i = 0; i < N; i++) {
  expression[i] = expression[i].split("+");
  for (let j = 0; j < expression[i].length; j++) {
    expression[i][j] = Number(expression[i][j]);
    sum += expression[i][j];
  }
  expression[i] = sum;
  sum = 0;
}
answer += expression[0];
for (let i = 1; i < N; i++) {
  answer -= expression[i];
}
console.log(answer);