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