백준] 1541 - 잃어버린 괄호

시간 제한 : 2초
메모리 제한 : 128MB

 

 

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

 

 

출력

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

 

 

소스코드

#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main(void)
{
	int len, start, end;
	string str, substr="";
	vector<int> intArr;
	vector<char> opArr;

	cin >> str;
	len = str.length();
	start = 0;
	for (int i = 0; i < len; i++)
	{
		if (str[i] == '+' || str[i] == '-')
		{
			end = i;
			substr = str.substr(start, end - start);
			start = i + 1;
			intArr.push_back(stoi(substr));
			opArr.push_back(str[i]);
		}
		else if (i == len - 1)
		{
			substr = str.substr(start, len - start);
			intArr.push_back(stoi(substr));
		}
	}

	int opSize, opFlag = 1, ans = intArr[0];
	opSize = opArr.size();
	for (int i = 0; i < opSize; i++)
	{
		if (opArr[i] == '+')
		{
			if (opFlag)
				ans += intArr[i + 1];
			else
				ans -= intArr[i + 1];
		}
		else
		{
			if (opFlag)
			{
				opFlag = 0;
				ans -= intArr[i + 1];
			}
			else
			{
				ans -= intArr[i + 1];
			}
		}
	}

	cout << ans;
}

 

Tip

그리디 문제인데, 생각은 쉽지만 구현이 어려울 수도 있는 문제지만, 문제에 허점이 있다. 사실 괄호의 수가 제한이 없기 때문에 연산자 '-'가 나오는 순간부터는 계속 값을 빼서 최저값을 구하면 된다.