[백준/1541번/node.js] 잃어버린 괄호

문제

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

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

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

입력

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

출력

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

예제 입력

55-50+40

예제 출력

-35

---

서론

오랜만에 올리는 알고리즘 문제풀이 포스팅이다. 그동안은 C++을 통해서 알고리즘 문제를 풀었는데, 작년 웹개발 인턴 활동을 하게 된 뒤로는 아무래도 js와 java를 많이 사용하다보니 js와 java로 알고리즘 문제를 푸는 게 더 편하고 익숙해졌다. 따라서 지금부터는 js로 문제를 풀 생각이다. 프로그래머스에서는 js로도 문제를 쉽게 풀 수 있지만, 백준에서는 js로 문제를 풀기 위해서 별도의 입출력 환경을 구성해야 하기 때문에 첫 문제는 어렵지 않도록 무난한 문제로 가져왔다. 따라서 이번 문제에는, js로 백준에서 요구하는 입출력을 원활히 사용할 수 있는가.. 이런 일종의 추가 과제가 나에게 주어졌다고 생각할 수도 있을 것 같다.

풀이에 사용할 알고리즘 구상

세준이는 항상 원하는 위치에 괄호를 적절히 배치할 수 있다. 그리고, 식의 값을 최소로 만들기 위해선, 최대한 많은 수를 음수로 만들어야 한다. 이 두 점을 명심한다면, 원하는 위치에 괄호를 배치해서 최대한 많은 수를 음수로 만드는 방법을 생각해야 한다는 점을 알 수 있고, 그 점은 다음과 같다.

식에서 처음 -(마이너스)가 등장한 뒤의 모든 수는 괄호를 적절히 배치해서 전부 음수로 만들 수 있다.

즉, 주어진 식에서 -(마이너스)를 찾고, 이 앞에 있는 모든 수는 (어쩔 수 없이) 더하고, 그 뒤의 모든 수는 빼면 된다. 나는 여기서 더할 수의 합을 plus, 뺄 수의 합을 minus로 정했다. 그리고 각각의 합을 구해줄 함수 summation을 만들어서 문제를 풀었다.

summation 함수를 만들 때, input이 없는 경우를 예외처리해준다면 그다지 어려운 문제가 아니다. +(플러스) 부호를 기준으로 split 메소드를 사용해서 모든 숫자를 구하고, 이에 대한 합을 reduce 메소드를 사용해 구하면 한 줄로도 코드가 끝난다.

제출 코드

// 입력 받기
const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString();

// 문제 풀이
function summation(input) {
        if (!input.length) return 0;
        return input.split('+').reduce((pre, val) => +pre + +val);
}

function solution(input) {
        let arr = input.split('-');
        let plus = summation(arr.shift());
        let minus = 0;
        for (let exp of arr) {
                minus += +summation(exp);
        }
        return plus - minus;
}

// 정답 출력
console.log(solution(input));

회고

문제를 다 푼 뒤 다른 사람들의 풀이를 구글링해본 결과, 자바스크립트에 대한 내 사랑이 더 커졌다. 항상 느끼는 점이지만 아무래도 자바스크립트가 문제를 짧고 간결하게 풀 수 있는데 큰 역할을 해 주는 것 같다. 또한 자바스크립트를 쓰면서 C++이나 java식으로 코드를 짜지 않도록 항상 자바스크립트스러운 코드를 작성하기 위해 노력하는데, 이 노력이 풀이에 잘 녹아들어간 것 같아서 뿌듯하게 문제를 푼 것 같다. 쉬운 문제긴 하지만.