BOJ 1541 잃어버린 괄호

문자열 파싱을 연습해볼수 있는 괜찮은 문제이다. 풀이 방법은 여러가지 존재하는데 보통 풀이는 다음과 같다.

최솟값을 만들기 위해 가능한 가장 큰 숫자를 빼야 한다. 따라서 - 를 기준으로 문자를 나누고 다음 - 를 만나기 전까지 모두 더해서 한번에 빼주면 된다.

 

나는 조금 고전적이지만 스택을 사용하여 숫자와 - 기호를 쌓았다. 이후 하나씩 빼면서 - 를 만나기 전까지 결과를 모두 더하고 - 를 만나면 더한 값을 -1곱하여 누적 시켜주었다.

 

#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<stack>
using namespace std;

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

	string s;

	cin >> s;

	stack<string> st;
	vector<int> v;
	int num = 0;
	int start = 0;
	int cnt = 0;
	for(int i = 0; i <= s.size(); i++)
	{
		string sub;
		if(s[i] == '+' || s[i] == '-' || i == s.size())
		{
			sub = s.substr(start, cnt);
			start = i + 1;
			cnt = 0;
		}
		else
		{
			cnt++;
			continue;
		}
		st.push(sub);
		if(s[i] == '-')
		{
			st.push("-");
		}
	}

	int minNum = 0;
	while(!st.empty())
	{
		string top = st.top();
		st.pop();
		if(top != "-")
		{
			num += stoi(top);
			continue;
		}
		else
		{
			num *= -1;
			minNum += num;
		}
		num = 0;
	}

	minNum += num;

	cout << minNum;
}