[C++][BAKJOON][수학] 1541번 잃어버린 괄호 풀이 & 반례

[문제]

1541번: 잃어버린 괄호

55-50+40 같은 식이 주어졌을 때, 괄호를 알맞게 쳐서 최소 합을 구하는 문제

예시 답은 55-(50+40) = -35 이다.

 

[문제풀이]

경우의 수를 여러개 만들어서 계산해보며 규칙을 찾아야 한다.

-가 없을 때, -가 가온데 껴있을 때, -가 계속 있을 때, - + 가 반복 될 때 등등...

 

10+11-5+4 = 10+11-(5+4) = 12

1+10-15-10+20-1 = 1+10-(15+10)+20-(1) = 5

 

위 두가지 경우를 살펴 보면, -가 나왔다면 그 뒤로 +가 나오거나 마지막 index에 다다를 때까지 괄호를 쳐서 빼주면 된다는 것을 알 수 있다.

 

[코드]

1) 식은 string으로 받고 string index를 사용해서 한글자씩 체크해준다.

2) 처음엔 +기호가 붙은 숫자가 들어올 것이므로 number 변수에 차곡차곡 string 숫자문자를 쌓아준다.

3) + , - 기호가 나오거나 string 마지막 index라면 지금까지 저장해둔 number를 result 변수에 더해준다. (맨첨은 양수)

    이 때, stoi() 함수를 사용해서 string을 int로 바꿔서 더해준다.

   3-1) -기호가 나왔다면,

          뒤에 +나 string 마지막 index에 다다를 때까지 계속해서 빼줘야 하므로 minus flag를 true로 체크해준다.

          그리고 - 뒤에 +가 나왔다면,

          현재 number까지만 빼주고 minus_flag를 false로 바꿔줘서 뒤에 나오는 숫자는 더할 준비를 한다.

   3-2) +기호가 나왔다면, 걍 더해준다.

4) 반복문 index가 문자열 길이와 같다면 마지막 엔터부분이므로 현재까지 구한 값을 마저 더하거나 빼주고 끝낸다. 

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

int main() {
	string str ="";
	cin >> str;
	
	string number = "";
	int result = 0;
	bool minus_flag = false;

	for (int i = 0; i <= str.length(); i++) {//****i를 str의 길이까지 포함해서 반복해줘야 함.
		if (str[i] == '+' || str[i] == '-' || i == str.length()) {
			if (minus_flag) {
				result -= stoi(number);
			}
			else {
				result += stoi(number);
			}
			minus_flag = (str[i] == '-') ? true : false;
			number = "";
		}
		else number += str[i]; //*****else 안써줘서 이상하게 연산한 것....
	}
	cout <<  result;

	return 0;
}