잃어버린 괄호 1541

문제 해설 및 주의사항

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

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

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

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

 

풀이

1. 아이디어

'-' 이후, '-' 이전 사이의 값들을 괄호 치면, 첫 '-' 부터는 모두 뺄 수 있다.

 

2. 입력 처리

- 문자열로 섞여있는 숫자와 더하기 빼기를 어떻게 잘 분리하느냐가 핵심이다.

풀이코드

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>
using namespace std;
// 1541 잃어버린 괄호

int main(){
	string s;
	cin >> s;
	// 수를 넣는 배열
	vector<int> num;
	// 부호를 넣는 배열
	vector<int> sign;
	int cur = 0;
	// 처음 숫자는 양수
	sign.push_back(1);
	
	// 문자열 처리
	for(int i = 0; i < s.size(); i++){
		// 부호일 경우
		if(s[i] == '+' || s[i] == '-'){
			if(s[i] == '+'){
				sign.push_back(1);
			}
			else{
				sign.push_back(-1);
			}
			
			// 지금까지의 숫자를 넣어줌
			num.push_back(cur);
			cur = 0;
		}
		
		// 숫자일 경우
		else{
			cur = cur * 10 + (s[i] - '0');
		}
	}
	
	// 마지막엔 부호가 없으므로 마지막 숫자를 넣어줌
	num.push_back(cur);
	int ans = 0;
	int minus = 1;
	
	for(int i = 0; i < num.size(); i++){
		if(sign[i] == -1){
			minus = -1;
		}
		ans += num[i] * minus;
	}
	
	cout << ans << endl;
	
}

 

---

퇴고