BOJ 1541 - 잃어버린 괄호 문제풀이

문제를 읽고 이해하기

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

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

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

입력

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

출력

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

재정의와 추상화

주어진 식에 괄호를 적절히 쳐서 최솟값을 만들기 위해서는 빼는 수가 최대가 되게 만들면 된다.

따라서, -가 나오기 전까지 모두 더했다가, -가 나오면 다음 -가 나오기 전까지 - 이후의 수의 합을 구한다. 그리고 그 수를 총합에서 뺀다. 다음 -가 나오면 이 과정을 반복하고, 만약 다음 -가 나오지 않으면, 수식의 끝까지 간 경우이므로 함수를 종료한다.

필자는 이 기능을 구현하기 전에, string으로 읽어들인 문자열을 Tokenize 하는 작업을 거쳤다. int형 vector에 숫자는 숫자로, 부호는 -면 -1, +면 -2로 저장해놓았다.

그리고, 토큰화된 정수와 부호(-1, -2로 표현됨)를 읽고 최솟값을 만들어내는 함수를 만들었다.

코드 작성

#include <iostream>
#include <vector>
using namespace std;

vector<int> tokens;

void tokenize(string target) {
    auto it = target.begin();
    while (it != target.end()) {
        if (*it == '-') {
            tokens.push_back(-1);
            it++;
        } else if (*it == '+') {
            tokens.push_back(-2);
            it++;
        } else {
            auto begin = it;
            for (; *it >= '0' && *it <= '9'; it++) {}
            tokens.push_back(stoi(string(begin, it)));
        }
    }
}

int minimized_value() {
    int total = *tokens.begin();

    auto it = tokens.begin() + 1;
    while (it != tokens.end()) {
        if (*it == -1) {
            it++;
            int temp = 0;
            for (;*it != -1 && it != tokens.end(); it++) {
                if (*it != -2) {
                    temp += *it;
                }
            }
            total -= temp;
        } else if (*it == -2) {
            total += *(++it);
            it++;
        } else {
            total += *it;
            it++;
        }
    }
    return total;
}

int main() {
    string input;
    cin >> input;
    tokenize(input);
    cout << minimized_value();
    return 0;
}