(백준 c++)1541 잃어버린 괄호

문제

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

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

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

입력

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

출력

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

 

 

 

문자열을 파싱하면서 최소값으로 만들도록 int형 벡터에 수를 저장하면 된다.

파싱하면서 -, + 기호를 확인하면서 진행.

만약 -가 나오면 앞에서 + 기호가 있었는지 plus 변수를 통해 확인.

plus가 true라면 지금까지 더한 값(sum)을 v 벡터에 삽입.

plus가 false라면 현재 숫자(tmp)를 v 벡터에 삽입.

 

파싱이 끝난 후 다시 한 번 plus를 확인하여 v에 수를 넣어준다.

그리고 v 벡터를 순회하면서 첫 번째 수를 제외한 모든 수를 빼주면 된다.

시작 수는 첫번째 값이기 때문이다.

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

int main(void){
    string s, tmp = "";
    int ans = 0, sum = 0;
    vector<int> v;
    bool plus = false;

    cin >> s;

    //문자열 파싱
    //-가 나오면 앞에서 + 기호가 있는지 확인.
    //만약 +가 앞에 있었다면 지금까지 더한 값을 v에 삽입
    //만약 +가 앖에 없었다면 현재 값을 v에 삽입
    for(int i = 0; i < s.size(); i++){
        if(s[i] == '-'){
            if(plus){
                sum += stoi(tmp);
                v.push_back(sum);
                sum = 0;
            }
            else{
                v.push_back(stoi(tmp));
            }
            tmp = "";
            plus = false;
        }
        else if(s[i] == '+'){
            sum += stoi(tmp);
            plus = true;
            tmp = "";
        }
        else{
            tmp += s[i];
        }
    }

    if(plus){
        sum += stoi(tmp);
        v.push_back(sum);
    }
    else{
        v.push_back(stoi(tmp));
    }

    //ans에 처음 값 저장
    ans = v[0];

    //v에 저장되어 있는 값 모두 뺄셈 진행
    for(int i = 1; i < v.size(); i++){
        ans -= v[i];
    }

    cout << ans;

    return 0;
}