[알고리즘 풀이 분석] BOJ 1541 잃어버린 괄호

오늘 풀어본 문제는 BOJ 1541 잃어버린 괄호 이다. 그리디 문제였는데 사실 그리디를 적용하기엔 비교적 간단한 문제였던 것 같다.

BOJ 1541 잃어버린 괄호

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

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

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

입출력

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

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

나의 풀이

적절하게 수들을 묶어서 가장 최솟값이 되도록 하는 문제이다.

처음엔 모든 경우의 수를 확인하는 단순한 방법도 생각했다가 생각해보니 나오는 연산자가 +, - 두가지 뿐이었다. 때문에 - 뒤에 나오는 수들을 제일 커지도록 해주면 되는 문제였다.

먼저 입력값은 문자열로 주어지기 때문에 연산자를 기준으로 나누어서 00009 와 같은 문자열을 9와 같이 변환해서 vector<string> token 에 담아준다.

이후 잘린 토큰들을 탐색하면서 연산을 진행하는데 - 부호가 나온다면, 다음에 또 -가 나올 때 까지 나오는 수들을 모두 더해준다. 이때 연산자는 +, - 두가지 뿐이므로 다른 경우를 생각할 필요가 없다.

더해준 값을 지금까지의 연산 값에서 빼주고 다시 탐색을 진행하면 최소의 결과를 얻을 수 있다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <stack>

// boj 1541 잃어버린 괄호, greedy, 실버 2
using namespace std;

int makeMinResult(string input){
    vector<string> token;

    // 연산 식 잘라서 배열에 담기 
    int from = 0;
    for (int i = 1; i < input.size(); ++i) {
        if (input[i]=='+'|| input[i]=='-'){
            int num = stoi(input.substr(from, i-from));
            token.push_back(to_string(num));
            token.push_back(input.substr(i, 1));
            i++;
            from = i;
        }
    }
    int num = stoi(input.substr(from, input.size()-from));
    token.push_back(to_string(num));

    int at = 0, answer =0;

    while (at<token.size()){
        if (token[at]=="+") at++;  // + 부호는 넘어가고 

        else if (token[at]=="-"){ // -부호가 등장하면 다음 - 까지 모두 더해서 결과값에서 빼주기 
            at++;
            int sum = 0;

            while (at<token.size() && token[at] != "-"){
                if (token[at] == "+") at++;
                else sum += stoi(token[at++]);
            }
            answer -= sum;
        }else answer += stoi(token[at++]);  // - 연산에 걸리지 않는 수는 더해주기 
    }
    return answer;
}

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    string input;
    cin>>input;

    cout<<makeMinResult(input);

   return 0;
}