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

문제

그리디 알고리즘 문제이므로 역시 최적해를 찾아야한다.

• 최적해 : ( - ) 가 발견되면, 그 뒤로 모든 원소는 다 괄호에 넣어주면 됨

풀이

• 연산기호가 포함되어 있으므로 string으로 입력값 받음
• split 후 각각 조건에 따라 plus, minus vector에 넣어줌
• 대략 네 가지 조건을 활용했다
  • minus를 못만나서 plus인 상태 ( + , flag = 1 )
  • minus를 최초로 만난 상태 ( - , flag = 0 )
  • minus를 이미 만난 상태 ( + or - , flag = 0)
  • 마지막 원소

#include <iostream>
#include <string>
#include <cstring>
#include <vector>

using namespace std;

int main()
{
    string numbers;
    vector<int> plus;
    vector<int> minus;
    cin>>numbers;
    int flag = 1; // plus : 1 , minus : 0
    int previousIndex = 0; 
    int temp = 0;

    for(int i=0;i<numbers.length();i++) {
        if(numbers.at(i) == '+' || numbers.at(i) == '-' ) {
            temp = stoi(numbers.substr(previousIndex, i)); // string to integer
            previousIndex = i+1;
            // 아직 minus 못만난 경우
            if(numbers.at(i) == '-' && flag == 1) {
                flag = 0;
                plus.push_back(temp);
            }
            else if(numbers.at(i) == '+' && flag == 1) {
                plus.push_back(temp);
            }
            // minus 만난 경우
            else if(flag == 0) {
                minus.push_back(temp);
            }
        }
    }
    // 마지막 숫자
    if(flag == 0) {
        temp = stoi(numbers.substr(previousIndex, numbers.length()));
        minus.push_back(temp);
    }
    else {
        temp = stoi(numbers.substr(previousIndex, numbers.length()));
        plus.push_back(temp);
    }
    int sum = 0;
    for(int i=0;i<plus.size();i++) sum += plus[i];
    for(int i=0;i<minus.size();i++) sum -= minus[i];

    cout<<sum<<endl;
    return 0;
}