백준1541 잃어버린 괄호

작성일 | In

문제 링크

  • http://icpc.me/1541

사용 알고리즘

  • 그리디

시간복잡도

  • O(N)

풀이

덧셈을 하면 숫자가 커지고, 뺄셈을 하면 숫자가 작아집니다.
작은 수를 빼면 조금 작아지고, 큰 수를 빼면 많이 작아집니다.

그러므로 덧셈을 먼저하고 뺄셈을 해주면 큰 수를 빼게 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;

const int MINUS = -1e9;
const int PLUS = 1e9;

vector<int> v;

int main(){
	string s; cin >> s; s += "+";
	int now = 0;
	for(auto i : s){
		if(i == '+' || i == '-'){
			if(v.empty()){
				v.push_back(now); now = 0;
			}else{
				int op = v.back(); v.pop_back();
				if(op == MINUS){
					v.push_back(now); now = 0;
				}else{
					int res = v.back(); v.pop_back();
					v.push_back(res + now); now = 0;
				}
			}
			if(i == '+') v.push_back(PLUS);
			else v.push_back(MINUS);
		}else{
			now *= 10; now += i-'0';
		}
	}
	v.pop_back();

	int ans = v[0];
	for(int i=1; i<v.size(); i++) ans -= v[i];
	cout << ans;
}