6) 백준 1541 - 잃어버린 괄호

<문제>

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

1541번: 잃어버린 괄호

개인적으로 생각보다 까다로웠던 것 같다.

 

<코드>

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

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cout.tie(NULL);
	cin.tie(NULL);
	
	vector<int> exp;
	vector<char> cal;
	string s, nums;
	cin >> s;
	
	for(int i = 0; i < s.size(); i++) {
		if(s[i] == '-') {
			int a = stoi(nums);
			exp.push_back(a);
			cal.push_back('-');
			nums = "";
		}
		else if(s[i] == '(' || s[i] == ')') {
			continue;
		}
		else if(s[i] == '+') {
			int a = stoi(nums);
			exp.push_back(a);
			cal.push_back('+');
			nums = "";
		}
		else {
			nums += s[i];
		}
		
	}
	
	exp.push_back(stoi(nums));
	
	for(int i = 0; i < exp.size()-1; i++) {
		if(cal[i] == '+') {
			exp[i+1] += exp[i];
			exp[i] = 0;
		}
	}
	int total = 0;
	int i = 0;
	while(exp[i] == 0) {
		i++;
	}
	total += exp[i];
	i++;
	for(i; i < exp.size(); i++) {
		total -= exp[i];
	}
	
	cout << total;
    
    return 0;
	
}

나의 방식은 이러했다.

간단히 우선순위를 '+'먼저 두고, '-'는 나중에 되도록 정했다.

 

string에서 숫자와 기호를 다른 vector에다 저장했다.

exp vector에는 숫자를, cal vector에는 기호를 저장했다. (물론, string에서 괄호가 나오면 패스)

cal에서 덧셈이 나오면 덧셈을 기준으로 앞은 0으로, 뒤는 더한 값을 저장해줬다. (erase를 쓸까 했지만 시간이 오래 걸릴 것 같아서 하지 않았다.)

뺄셈이 나오면 그냥 패스 했다.

 

후에 0이 아닌 가장 앞에 있는 숫자를 찾고 그 수에서 저장된 모든 값들을 전부 빼줬다.

 

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

시간이 오래 걸릴까 했지만 무슨 일인지 통과됐다. 기분이 좋다!

그런데 그리디를 할 때마다 더욱 코드를 줄일 수 있을 듯싶은데.... 아쉬운 기분....