잃어버린 괄호 (feat. 백준, 1541번)

잃어버린 괄호
https://www.acmicpc.net/problem/1541

1541번: 잃어버린 괄호

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	string str;
	cin >> str;
	vector<string> str_tmpl;
	auto minus_sign = str.find('-');
	while (minus_sign != string::npos) {
		str_tmpl.push_back(str.substr(0, minus_sign));
		str.erase(0, minus_sign + 1);
		minus_sign = str.find('-');
	}
	str_tmpl.push_back(str);

	vector<int> tmp;
	for (auto& item : str_tmpl) {
		auto value = 0;
		auto plus_sign = item.find('+');
		while (plus_sign != string::npos) {
			value += stoi(item.substr(0, plus_sign));
			item.erase(0, plus_sign + 1);
			plus_sign = item.find('+');
		}
		value += stoi(item);
		tmp.push_back(value);
	}
	register int ans = tmp[0];
	for (register int i = 1; i < tmp.size(); ++i)
		ans -= tmp[i];
	cout << ans;
	return 0;
}
// *&)*@*

1. 괄호를 붙였을때 가장 작은 값을 출력하는 문제입니다.
2. 가장 작은 값은 큰 값을 뺄수록 작아집니다.
3. 따라서 + 연산을 먼저 수행하고 + 연산이 수행된 정수와 수행되지 않은 정수끼리의 - 연산이 이루어지면 가장 작은 정수값이 됩니다.
4. 첫 번째 케이스인 '55-50+40' 을 예로 보겠습니다.
5. 먼저 문자 '-'로 split 를 취합니다. 그럼 '55' 와 '50+40' 이 남게 됩니다.
6. '55' 에서 문자 '+' 로 split을 취한 뒤 더해줍니다. 결과는 '55' 입니다.
7. '50 + 40'에서 문자 '+'로 split을 취한 뒤 더해줍니다. 결과는 '90' 입니다.
8. 남겨진 정수는 순서대로 '55', '90' 입니다.
9. '55' - '90' 을 취한 뒤 이를 출력합니다.