[백준/C++] 1541번 : 잃어버린 괄호 (그리디, 문자열 문제)

잃어버린 괄호 

문제

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.

그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.

괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

입력

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

출력

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

예제 입력 1

55-50+40

예제 출력 1

-35

예제 입력 2

10+20+30+40

예제 출력 2

100

예제 입력 3

00009-00009

예제 출력 3

0

---

해당 문제는 입력받는 수식 string을 멋대로 괄호 쳐서 결과 값을 최소로 만들어야 한다.

 

처음에는 "55-50+40"으로 입력받는 문자열에서 숫자 55, 50, 40을 vector에 저장하고, 연산자 -, + 를 vector에 저장하여 각각의 index? 값의 규칙을 찾으려 했다.

 

대충 노력한 흔적..

그러나 문제의 해결책은 생각보다 너무너무 쉬웠다 !

 

앞에서부터 연산을 수행하다가 연산자가 마이너스(-)가 나오는 순간부터 뒤에 모든 숫자를 뺄셈으로 연산하면 된다.

- 가 하나라도 있으면 뒤에 +가 있든, - 가 있든 여러개가 있든 한개가 있든 상관없이 괄호를 통해 전부 뺄셈으로 바꿀 수 있다.

 

ex) 55 - 50 + 40 - 30 + 20

=> 55 - (50 + 40) - (30 + 20)

 

5 + 20 - 50 + 20 + 10 + 4 - 40 - 20

=> 5 + 20 - (50 + 20 + 10 + 4) - 40 - 20

 

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

using namespace std;

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

	string str;
	cin >> str;

	string numStr = "";
	int result = 0;
	bool isMinus = false;
	for (int i = 0; i <= str.size(); i++)
	{
		if (str[i] == '-' || str[i] == '+' || i == str.size())
		{
			if (isMinus)
			{
				result -= stoi(numStr);
				numStr = "";
			}
			else
			{
				result += stoi(numStr);
				numStr = "";
			}
		}
		else // 숫자라면 누적 더하기
			numStr += str[i];

		if (str[i] == '-')
			isMinus = true;
	}

	cout << result;

	return 0;
}

 

따라서 정답 풀이는, string 변수에 받은 수식을 0번째 인덱스 부터 검사하다가, 마이너스가 나온 순간 bool isMinus 변수를 체크하고, 그 다음 숫자들부터 전부 뺄셈으로 처리하도록 조건문을 작성하였다.

---

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

1541번: 잃어버린 괄호