[c++] 백준 1541 - 잃어버린 괄호(그리디 알고리즘)

0. [c++] 백준

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

1. 풀이

한번 '-' 부호가 등장을 하면 그 뒤에 어떤 숫자와 부호가 등장하든 괄호를 이용해 모두 음수로 만들 수 있다.

이러한 원리를 이용해 숫자를 저장하는 스택을 만들고, 부호가 나올 때 마다 연산을 해주는 알고리즘을 짜보았다.

2. 소스코드

#include<iostream>

#include<algorithm>

#include<vector>

#include<string>

using namespace std;

int main() {

ios_base::sync_with_stdio(0);

cin.tie(0);

string N;

cin >> N;

int ret = 0;

bool flag = false;

int stack = 0;

for (int i = 0; i < N.length(); i++) {

if (N[i] == '+') {

if (flag) {

ret -= stack;

stack = 0;

}

else {

ret += stack;

stack = 0;

}

}

else if (N[i] == '-') {

if (flag) {

ret -= stack;

stack = 0;

}

else {

flag = true;

ret += stack;

stack = 0;

}

}

else {

stack *= 10;

stack += N[i] - 48;

}

//cout << stack << " " << ret << endl;

}

if (flag)

ret -= stack;

else

ret += stack;

cout << ret;

return 0;

}

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!