C++ / 백준 / 1541 / 잃어버린 괄호

문제

 

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

1541번: 잃어버린 괄호

 

문제풀이

 

괄호의 개수는 주어지지 않고 특별한 조건이 없는 걸로 봐선 무한으로 쓸 수 있다.

값을 최소로 만들려면 뺄셈을 최대한 많이 하는 것이 좋다.

그리고 코드를 줄이기 위해 입력을 받고 마지막에 '+' or '-'를 추가로 더한다.

 

처음 문자와 마지막 문자는 숫자이므로 첫 숫자는 무조건 덧셈을 해야 한다.

'-' 나오는 경우에 뒤에 '+'가 오면 앞의 '-'를 기준으로 묶어 둘 다 뺄셈을 하게 만든다

-10+20 => -(10+20)

 

'-' 다음 '-'이 나온다면 특별히 괄호를 안 해도 된다.

이런 식으로 보다 보면 한번 '-'가 나온 이후에는 뒤에 어떤 연산자가 오든 뺄셈만 하면 된다는 것을 알게 된다.

 

반복문을 통해 숫자를 파싱 하고, 연산자를 만났을 때 이전 연산자 중에 뺄셈이 있었는지, 없었는지 확인 하면 된다.

 

코드

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

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

	int idx(0), sum(0);
	string expression("");
	string s_num("");
	bool minus(false);

	cin >> expression;
	expression += '+';

	for (idx = 0; idx < expression.size(); ++idx) {
		if (expression[idx] == '-' || expression[idx] == '+') {
			minus == true ? sum -= stoi(s_num) : sum += stoi(s_num);

			if (expression[idx] == '-') {
				minus = true;
			}
			s_num = "";
		}
		else {
			s_num += expression[idx];
		}
	}

	cout << sum;
}