BOJ 1541 - 잃어버린 괄호

문제 링크

문제#

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

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

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

입력#

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

출력#

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

풀이#

식을 최소로 만들려면 첫 번째 -가 나온 뒤의 값들은 가능한 한 전부 한꺼번에 빼야 한다. 즉 수식을 - 기준으로 끊고, 각 조각 안의 + 값들을 먼저 합한 뒤 첫 조각만 더하고 나머지는 전부 빼면 된다.

현재 코드는 문자열을 직접 읽으며 수를 만들고, -를 만나는 순간 누적값을 정리한다. 괄호를 실제로 넣어 보지 않아도 '첫 빼기 이후는 다 묶어서 뺀다'는 관찰만 있으면 구현이 간단해진다.

코드#

#include <iostream>
#include <string>
using namespace std;
 
void solve() {
	string s;
	cin >> s;
	
	bool is_minus = false;
	int size = s.size();
	int answer = 0;
	string num = "";
 
	for (int i = 0; i <= size; i++) {
		if (s[i] == '+' || s[i] == '-' || i == size) {
 
			if (is_minus) {
				answer -= stoi(num);
			}
			else {
				answer += stoi(num);
			}
 
			if (s[i] == '-')
				is_minus = true;
 
			num = "";
		}
		else 
			num += s[i];
	}
 
	cout << answer << '\n';
}
 
int main() {
 
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
 
	solve();
 
	return 0;
}

복잡도#

• 시간 복잡도: 식 문자열을 한 번 훑으므로 길이를 $L$이라 할 때 $O(L)$이다.
• 공간 복잡도: 현재 숫자 문자열만 저장하므로 $O(L)$이다.

마무리#

첫 번째 - 뒤의 덧셈 묶음을 모두 빼는 순간 식의 값이 최소가 된다. 괄호를 직접 만들지 않아도 부호 상태만 기억하면 같은 효과를 낼 수 있다.