[백준 1541] 잃어버린 괄호

🔗알고리즘 문제

오랜만에 해결한 그리디 문제 그리디는 자신이 없어서 실버 문제이지만 안풀고 남겨뒀었는데 이제 더이상 남겨둘 수 없어서 풀게되었다.

문제 분석

괄호가 제거된 수식이 주어질 때 괄호를 추가하여 값이 가장 작아지는 경우를 찾으면 된다.

발상 & 알고리즘 설계

이 문제를 풀기 위해 수식에서 가장 작은 값이 나오는 경우는 작은 수에서 큰 수를 뺄 때임을 알아야 한다.

따라서 이 문제에서도 더하기를 모두 해준뒤에 뺄셈을 진행하면 가장 작은 값을 구할 수 있다.

전체 문자열을 -를 기준으로 나누어주고 나누어서 생긴 문자열 속 숫자들을 모두 더해준 뒤에 answer에서 빼주었다.

한가지 유의해야 할 점은 첫 번째 숫자에도 음수가 나올 수 있다는 것이다. 따라서 해당 경우는 따로 처리해주었다.

코드

#include<iostream>
#include<vector>

using namespace std;

vector<string> split(string &s, char target){
    vector<string> v;

    for(int i = 0; i < s.length(); i++){
        if(v.empty() || s[i] == target)
            v.push_back("");

        if(s[i] == target)
            continue;

        v[v.size() - 1].push_back(s[i]);
    }

    return v;
}

int sum(const vector<string> &v){
    int val = 0;

    for(int i = 0; i < v.size(); i++){
        val += stoi(v[i]);
    }

    return val;
}

int main()
{
    vector<string> splitString;
    string s;

    int answer = 0;

    cin >> s;

    splitString = split(s, '-');

    int temp = sum(split(splitString[0], '+'));
    if(s[0] == '-'){
        answer -= temp;
    }
    else{
        answer += temp;
    }

    for(int i = 1; i < splitString.size(); i++){
        answer -= sum(split(splitString[i], '+'));
    }

    cout << answer;
}