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

1541번: 잃어버린 괄호

cpp

#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의 인덱스 순회 한번으로 푸는 방법도 존재했습니다.