[그리디] 백준 1541 잃어버린 괄호 C++

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

1541번: 잃어버린 괄호

---

---

문제자체는 간단한데 포스팅하는 이유는 풀이과정에서 코드가 긴거 같아 찾아보니 코드를 줄일 수 있는 방법이 있었다

일단 접근방법은 괄호를 사용해서 최솟값이 되게하는 것이므로 -기호가 나온 이후부터 숫자를 계속 빼주면된다! 왜냐

예를 들어 10 - 20 + 30 -40 -50=? 이라는 식이 있다고 가정할 때 최솟값을 찾으려면 10 - ( 20 + 30 ) - 40 - 50 이된다.

즉, 중간의 +연산을 묶어 - 로 만들 수 있다. 그러므로 -가 나온 이후 - 연산은 그냥 빼면 되고 + 연산은 괄호를 묶어 -연산으로 바꾸면 된다는 것이다. 코드 상에서 - 가 나온 이후 시점이라는 것을 알기 위해 flag 변수를 사용했다.

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

using namespace std;
vector<string> vec;
int main() {
	string s;
	cin >> s;
	string tmp = "";
	for (int i = 0; i <= s.size(); i++) {
		if (i == s.size()) {
			vec.push_back(tmp);
		}
		if (s[i] == '+' || s[i] == '-') {
			vec.push_back(tmp);
			tmp = s[i];
			vec.push_back(tmp);
			tmp = "";
		}
		else {
			tmp += s[i];
		}
	}
	int rst = 0;
	int flag = 1;
	for (auto a : vec) {
		if (flag == 1) {
			if (a == "+") {
				continue;
			}
			else if (a == "-") {
				flag = 0;
			}
			else {
				rst += stoi(a);
			}
		}
		else {
			if (a == "+" || a == "-") continue;
			rst -= stoi(a);
			
		}
	}
	cout << rst << endl;
}

이렇게 제출 해서 정답을 맞췄는데 코드가 쓸데 없이 긴 것같아 다른 정답을 찾아보니 2배 가까이 줄일 수 있었다.

나는 입력에서 띄어쓰기 없이 문자열 통으로 입력되기 때문에 이를 string vector에 각각 숫자와 연산자를 따로 구분하여 파싱해준 다음에 다시 vector를 반복문을 통해 돌면서 연산을 해줬는데 이과정을 한번에 처리할 수 있다.

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

using namespace std;
int main() {
	string s;
	cin >> s;
	string tmp = "";
	int rst = 0;
	int flag = 1;
	for (int i = 0; i <= s.size(); i++) {
		if (s[i] == '+' || s[i] == '-' || i == s.size()) {
			if (flag == 1) {
				rst += stoi(tmp);
			}
			else {
				rst -= stoi(tmp);
			}

			if (s[i] == '-')  flag = 0;

			tmp = "";
			continue;
		}
		tmp += s[i];
	}

	
	cout << rst << endl;
}