1541 잃어버린 괄호

www.acmicpc.net/problem/1541

1541번: 잃어버린 괄호

 

<아이디어>

가장 처음과 마지막은 숫자이고, 두 개 이상의 연산자는 나타나지 않는다. 

그럼 숫자가 N개라면 연산자는 N-1개이다.

숫자는 vector에, 연산자는 queue에 저장하고 숫자를 한칸씩 가면서 계산한다.

최솟값을 만들기 위해 '-'연산자 뒤에 나오는 '+'연산자에 해당하는 숫자들을 모두 더하여 한번에 뺀다.

 

 

경우의 수는 다음과 같다.

 -  queue에서 '-'가 나온 경우, 빼기 위해 저장되어있는 값을 결과값에서 뺀 다음 다시 저장한다.

 - queue에서 '+'가 나온 경우, 저장된 값이 있다면 (이전에 '-' 가 나왔다면) 저장된 값에 더한다.

 - queue에서 '+'가 나왔지만 저장된 값이 없다면 결과값에 더한다.

 

마지막에 빼기위해 저장된 값을 결과값에서 뺀다.

 

 

#include <bits/stdc++.h>
using namespace std;
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
typedef long long lld;
 
int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    
    string s;
    cin>>s;
    
    vector<int> v;
    queue<char> op;
    v.push_back(0);
    for(int i=0;i<s.length();i++)
    {
        if(s[i]=='-' || s[i]=='+')
        {
            op.push(s[i]);
            v.push_back(0);
        }
        else if(s[i]>='0' && s[i]<='9')
        {
            *(v.end()-1) *= 10;
            *(v.end()-1) += s[i]-'0';
        }
    }
 
 
    lld ans = (lld)v[0], sub = 0;
    for(int i=1;i<v.size();i++)
    {
        if(op.front()=='-')
        {
            ans -= sub;
            sub = 0;
            sub += v[i];
        }
        if(op.front()=='+')
        {
            if(sub) sub += v[i];
            else ans += v[i];
        }
        op.pop();
    }
    if(sub) ans -= sub;
    cout<<ans;
 
 
    return 0;
}