백준 1541. 잃어버린 괄호 (그리디)

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

1541번: 잃어버린 괄호

1. 특징

1) 그리디

2) 구현

 

2. 구현 방식

1) 그리디조건: -와 - 사이의 +는 모두 합해준다.

55-50+3+2+40-4-3 

이면, 55-(50+3+2+40)-4-3을 해준다. 

2) split 함수를 이용하여, '+', '-'를 기준으로 숫자를 나눈다. 

+: 처음으로 - 뒤의 + 가 등장하면: sum = tmp의 숫자

    연속으로 +가 등장하면: sum+= tmp의 숫자

-: sum이 0이아니라면(해당연산자(-)의 앞연산자가 +였다는 의미): sum += tmp의 숫자, 벡터에 sum 넣기, sum = 0

    sum 이 0이라면: 벡터에 tmp넣기

그리고 마지막 연산자를 기억해서 이에 따른 처리를 해준다. 

3) split 함수에 의해 만들어진 벡터의 모든 숫자에 - 연산을 해준다.

 

3. 코드

#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>
#include<algorithm>
using namespace std;

string str;
int ans;
vector<int> num;
void split()
{
    string tmp = "";
    int sum = 0;
    int last = 0;
    for(int i = 0; i < str.size(); i++)
    {
        if(str[i] == '-')
        {
            if(sum != 0)
            {
                sum += stoi(tmp);
                num.push_back(sum);
                sum = 0;
            }
            else
            {
                num.push_back(stoi(tmp));
            }
            last = 0;
            tmp = "";

        }
        else if(str[i] == '+')
        {
            if(sum==0) sum = stoi(tmp);
            else sum += stoi(tmp);
            last = 1;
            tmp = "";
        }
        else
        {
            tmp += str[i];
        }
        
    }
    if(last == 0)
    {
        num.push_back(stoi(tmp));
    }
    else
    {
        sum += stoi(tmp);
        num.push_back(sum);
    }


}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> str;
    split();

    int answer = num[0];

    for(int i =1; i < num.size(); i++)
    {
        answer -= num[i];
    }
    cout << answer;

}

 

4. 남의 코드

- 뒤의 +를 모두 -로 바꿔주면, 문제를 더 간단하게 풀수있었다.

https://beginnerdeveloper-lit.tistory.com/116

[C++] 백준 1541번 잃어버린 괄호