[백준] C++ 1541번 잃어버린 괄호 실버2 - Greedy Algorithm

문제 : https://www.acmicpc.net/problem/1541
분류 : Greedy Algorithm(그리디 알고리즘)

접근

1. 괄호를 어디든 만들 수 있다는 뜻은 -가 나오면 모든 값을 -로 바꿀 수 있다는 뜻이다.

   예를 들어 20-40+50+10가 나오면 20-(40+50+10)으로 만들 수 있다. 즉 20-40-50-10과 같다.
   문제의 예로 50-55+40은 50-(55+40)이기 때문에 50-55-40이다.

2. 때문에 -가 나오면 그 뒤로는 모두 -로 계산하면 된다.

슈도코드

input str
for str.length:
  if - or + or end:
    if -:
      answer -= int(temp)
    else:
      answer += int(temp)
    
    if -:
      flag true
    
    temp reset
  else:
    temp += str[i]

풀이

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int calc(string str, string temp) {
	int answer = 0;
	bool minus = false;

	for(int i = 0; i <= str.length(); i++) {
		if (str[i] == '-' || str[i] == '+' || i == str.length()) {
			if(minus) {
				answer -= stoi(temp); // string to int
			} else {
				answer += stoi(temp);
			}
			
			temp = "";
			if (str[i] == '-')
				minus = true;
		} 
		else {
			temp += str[i];
		}
	}
	
	return answer;	
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	string str, temp = "";
	cin >> str;	
	
	cout << calc(str, temp);
	return 0;
}