Algorithm

[BOJ] 1541번 : 잃어버린 괄호

rudgh99_algo 2024. 9. 7. 14:04

1. problem : 

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

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
vector<char> syms;
vector<int> nums;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); 
	string s; 
	cin >> s; 
	char current_sym = '+';
	string num = "";
	for (int i = 0; i < s.length(); i++) {
		if (s[i] == '+') {
			if (current_sym == '-') s[i] = '-';
		}
		if (s[i] == '-') {
			current_sym = '-';
		}
	}
	syms.push_back('+');
	for (int i = 0; i < s.length(); i++) {
		if (s[i] == '+' || s[i] == '-') {
			syms.push_back(s[i]);
			nums.push_back(stoi(num));
			num = "";
		}
		else num += s[i];
	}
	nums.push_back(stoi(num));
	int ans = 0;
	for (int i = 0; i < nums.size(); i++) {
		if (syms[i] == '+') ans += nums[i];
		else ans -= nums[i];
	}
	cout << ans << '\n';
}

이 방법은 그리디를 이용한 풀이다. -를 보는순간 뒤에 있는 부호를 -로 바꾸는 과정이 포함된다. 

전반적으로 코드가 더럽다. 다음번에는 이러한 코드를 작성하지말고, 아래와 같은 코드를 작성하자. 

 

 

3. solution 2 :

#include <bits/stdc++.h>
using namespace std;
int tmp, ans;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); 
	string s; 
	cin >> s; 
	int sign = 1; 
	for (int i = 0; i < s.length(); i++) {
		if (s[i] == '+' || s[i] == '-') {
			ans += tmp * sign; 
			if (s[i] == '-') sign = -1; 
			tmp = 0;
		}
		else {
			tmp *= 10; 
			tmp += s[i] - '0';
		}
	}
	ans += tmp * sign;
	cout << ans << '\n';
}

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x11/solutions/1541.cpp

 

basic-algo-lecture/0x11/solutions/1541.cpp at master · encrypted-def/basic-algo-lecture

바킹독의 실전 알고리즘 강의 자료. Contribute to encrypted-def/basic-algo-lecture development by creating an account on GitHub.

github.com