[그리디 #2] BOJ1541 잃어버린 괄호

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

1541번: 잃어버린 괄호

 

첫번째 시도

덧셈을 먼저 진행 후, 나중에 뺄셈을 진행해야 한다고 생각해서 operands, operations Vector를 두 개 만들어 덧셈->뺄셈 순서로 진행하는 방법을 생각했지만 매우 비효율적인 방법으로 생각되어 다른 방법을 생각함

 

두번째 시도

뺄셈이 나오면 뒷부분의 +는 -로 바꾸어 계산하는 방법을 생각함. 그런데 -의 경우, 부호를 바꾸면 +가 되기 때문에 이를 고려해야 한다고 생각함.

 

예를 들어 30 - 50 + 40 - 30 + 20의 경우,

30 - (50 + 40) - (30 + 20) 가 -110으로 정답이지만,

30 - (50 + 40 - 30 + 20) 전혀 다른 답이 나온다.

 

따라서, -를 따로 처리해야 한다고 생각했다.

 

다른 블로그를 참고한 결과

+20은 -30의 -을 영향을 받기에 , -50의 -을 적용받던 -30의 -을 적용받던 상관이 없다.

-30의 경우 -50의 - 를 영향받지 않고, -30으로 계산되어야 하기 때문에,

앞쪽에서 한 번 -가 오면 뒷 부분은 무조건 - 로 바꾸어 계산을 하면

뒤 부분의 - 가 + 로 바뀌는 부분을 생각하지 않고 코드를 작성 할 수 있다.

 

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <string>

using namespace std;

vector<int> operands;
vector<char> operations;

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

	string str;
	cin >> str;

	string num;
	int res = 0;
	bool minus = false;

	for (int i = 0; i <= str.length(); i++) {
		if (str[i] == '+' || str[i] == '-' || i == str.length()) {
			if (minus) {
				res -= stoi(num);
				
			}
			else {
				res += stoi(num);

			}
			num = "";
		}
		else {
			num += str[i];
		}

		if (str[i] == '-')
			minus = true;
	}
	
	cout << res;

}