[백준 C++] 1541 잃어버린 괄호 - 그리디

1541번: 잃어버린 괄호

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

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	string Input;
	getline(cin, Input);

    // Split Two Set
	int SubtractIndex = Input.find('-');
    string SumString = Input.substr(0, SubtractIndex);
    string SubtractString = (SubtractIndex != string::npos) ? Input.substr(SubtractIndex + 1) : "0";

    // Parsing SumNumbers
    vector<int> SumNumbers;
    SumNumbers.reserve(50);
    int previous = 0;
    int current = min(SumString.find('-'), SumString.find('+'));
    while (current != string::npos) {
        string Buffer = SumString.substr(previous, current - previous);
        SumNumbers.emplace_back(stoi(Buffer));

        previous = current + 1;
        current = min(SumString.find('-', previous), SumString.find('+', previous));
    }
    SumNumbers.emplace_back(stoi(SumString.substr(previous, current - previous)));

    // Parsing SubtractNumbers
    vector<int> SubtractNumbers;
    SubtractNumbers.reserve(50);
    previous = 0;
    current = min(SubtractString.find('-'), SubtractString.find('+'));
    while (current != string::npos) {
        string Buffer = SubtractString.substr(previous, current - previous);
        SubtractNumbers.emplace_back(stoi(Buffer));

        previous = current + 1;
        current = min(SubtractString.find('-', previous), SubtractString.find('+', previous));
    }
    SubtractNumbers.emplace_back(stoi(SubtractString.substr(previous, current - previous)));

    // Solution
    int Result = 0;
    for (const int& Number : SumNumbers)
    {
        Result += Number;
    }
    for (const int& Number : SubtractNumbers)
    {
        Result -= Number;
    }
    cout << Result;
}

---

 

'-' 기호가 하나라도 있다면 그 뒤에 나오는 모든 숫자는 뺄셈으로 연산이 가능합니다. (적절히 괄호를 사용할 수 있기 때문)

따라서 최대한 많은 숫자를 뺄셈 연산으로 적용하도록 해서 최소값을 구했습니다.

 

구현 방식은 다음과 같습니다.

1. 처음으로 등장하는 '-' 기호를 기준으로 스트링 분리

2. 좌측에 있는 숫자들은 덧셈 연산을 위한 벡터에 저장

3. 우측에 있는 숫자들은 뺄셈 연산을 위한 벡터에 저장

4. 결과로 두 벡터의 합 출력

 

알고리즘보다 문자열 파싱 기법에 더 신경을 쓰게 된 문제입니다.

다른 분들의 풀이를 보니 find, substr 함수를 사용하지 않고도

입력받은 string의 인덱스 순회 한번으로 푸는 방법도 존재했습니다.