백준 1541 잃어버린 괄호 : C++

https://www.acmicpc.net/problem/1541

1541번: 잃어버린 괄호

 

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

using namespace std;

int main(){
    string expression, tempStr;
    vector<int> v;
    int sum = 0, tempNum = 0;

    cin >> expression;

    for(int i = 0; i < expression.length(); i++){
        tempStr += expression[i];
        if(expression[i+1] == '+' || expression[i+1] == '-' || i+1 == expression.length()){
            v.push_back(stoi(tempStr));
            tempStr = "";
        }
    }
    // 사이즈 -1 부터
    for(int i = v.size()-1; i >= 0; i--){
        if(v[i] <= 0 || i == 0){
            if(i == 0){
                sum += v[i] + tempNum; 
            }
            else{
                sum += v[i] - tempNum;
                tempNum = 0;
            }
        }
        else if(v[i] > 0){
            tempNum += v[i];
        }
    }

    cout << sum;
}

풀이과정 

1. expression으로 받은 모든 스트링을 정수로 변환화여 벡터로 재구성

2. 뒤에서 부터 탐색, 가장 작은 수를 만들기 위해선 - 되는 수가 커야하므로 음수를 만날 때 까지 양수들을 모두 저장

  ex ) 10 -5 +10 +20 +30 ==> 10 - (5 +10 +20 +30) 으로 변환

3. 음수를 만나지 못하고 첫 요소에 도달하면 저장한 양수를 더해준다.