백준 1541: 잃어버린 괄호 [C++]

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

 

+와 -로만 이루어진 식에서 순서를 적절히 하여 최솟값을 찾으라는 문제

값이 작아지려면 빼기를 많이 해주면 될 것이다.. 식 자체의 순서를 섞을 수는 없으므로, 마이너스가 등장했다면 그다음 마이너스가 나오기 전까지 모든 값을 더해준 뒤 빼주면, 가장 큰 값을 빼주는 것이 되므로 곧 최솟값이 될 것이다.

마이너스가 나왔는지 여부를 체크하며 적절히 구현해주면 해결된다.

 

전체 코드

#include <iostream>
#include <string>

using namespace std;

int solution(string str){
    int answer=0;
    string tmp = ""; //피연산자 임시로 저장할 스트링
    bool flag = false; //마이너스가 등장했는지 여부
    
    for(int i=0;i<=str.length();i++){
        if(str[i] == '-' || str[i] == '+' || i==str.length()){ //연산자 or 식이 끝남(끝났다면 현재까지 저장되어있던 tmp값을 처리해줘야 하므로)
            if(flag){
                answer -= stoi(tmp);
            } else {
                answer += stoi(tmp);
            }
            tmp = ""; //임시 문자열 초기화
        }
        else { //숫자(피연산자)
            tmp += str[i];
        }
        if(str[i]=='-') flag=true; //첫번째는 무조건 숫자이므로 조건을 첫 시도 아래에 달아줌
    }
    return answer;
}

int main()
{
    string s;
    cin >> s;
    cout << solution(s);

    return 0;
}