뚝딱뚝딱

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

💡 잃어버린 괄호

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

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

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

✅ 문제 풀이

• 주어지는 수식에서 부호는 + 또는 - 밖에 주어지지 않는다.
• 따라서 -부호 뒤에 오는 수식은 다음 - 부호가 오기 전까지는 괄호로 묶어 전체를 -값으로 계산할 수 있다.
  이때의 값이 이 수식의 최소값이 될 것이다.
• 그럼 주어지는 수식에서 첫번째로 주어지는 -부호 이후에 오는 숫자들은 모두 -가 붙어서 계산된다고 생각할 수 있다.
• 따라서 첫번째 -부호가 부호들 중에서 몇번째로 등장하는지 카운트 해 줄것이다.
• 그리고 부호가 아닌 문자열은 숫자로 판단하여, temp라는 저장소에 계속해서 업데이트 하며 값을 계산할 것이고, 부호가 등장했을 때는 숫자값을 넣어두는 벡터에 temp값을 넣고, temp는 다시 0으로 초기화 해줄것이다.
• 이렇게 되면 마지막 숫자에 대해서는 부호로 끝나지 않기때문에, temp에 저장된 숫자 값이 벡터에 들어가지 않고 끝나기 때문에, 마지막에는 벡터에 temp값을 한번 더 추가해준다.
• 위의 과정은 입력으로 받는 문자열을 하나씩 탐색해가면서 판단하는 것이다.
• 문자열을 모두 순회한 뒤에는, 숫자가 담긴 벡터 arr와, 첫번째 -부호의 위치를 갖는 cnt가 결정되게 된다.
• 따라서 arr의 크기만큼 순회하면서, 현재 arr의 인덱스가 cnt이하이면 각각을 sum에 더하고, cnt를 초과하면서부터는 sum에서 빼는 방식으로 계산해주면 된다.
• 그럼 최종 최소값이 sum에 저장되고, 출력하면 된다.

#include<iostream>
#include<vector>
#include<string>

using namespace std;

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

	string str;
	cin >> str;

	int temp = 0;
	int res = 0;
	//한번 마이너스가 발생하고 나면 그 뒤로는 +에 대해서는 다 -로 묶을수 있으니까 마이너스 발생 후에는 모두 -로 계산

	vector<int> arr;
	int cnt = 0;
	int cntbreak = false;
	for (int i = 0; i < str.size(); i++) {
		if (str[i] != '+'&&str[i] != '-') {//숫자이면
			temp *= 10;
			temp += str[i] - '0';
		}
		else {
			arr.push_back(temp);
			temp = 0;

			if (!cntbreak&&str[i] == '+') cnt++;
			else if (str[i] == '-') cntbreak = true;
		}
	}

	arr.push_back(temp);

	for (int i = 0; i < arr.size(); i++) {
		if (i <= cnt) {
			res += arr[i];
		}
		else {
			res -= arr[i];
		}
	}

	cout << res;

	return 0;
}