[BOJ] 2023.02.05 #1541 잃어버린 괄호

오늘은 오랜만에 백준을 풀었다.

작년 1학기 알로하 회합 때 과제로 나갔었는데 안 풀었던 못 풀었던 문제들을 다시 보고 풀어봤다.

#1541. 잃어버린 괄호

tag: 수학, 문자열, 그리디, 파싱

문제링크

결과값을 최소로 만들어야하기 때문에, - 다음에 +가 연속으로 나오면 그 숫자들을 괄호로 묶어서 빼기되는 값을 최대한 크게 만들어야한다.

예를 들어 [50 - 20 + 30 + 10 - 5] 라는 수식이 있다면 [50 - (20 + 30 + 10) - 5] 이렇게 묶어서 값이 최소가 될 것이다.

생각은 금방 났지만 파싱이 좀 귀찮았던 것 같다… 문자열을 int로 변환하는 것은

string s = "123";
stringstream ssInt(s);
int i;
ssInt >> i;

이런식으로 변환하는 방법이 있길래 이렇게 했다.

파싱을 다 해서 숫자는 int 벡터(operands)에, +,-는 char 벡터(operators)에 각각 넣어놓고 구현을 시작했다.

#include <bits/stdc++.h>
using namespace std;

vector<int> operands;
vector<char> operators;

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

    string s; cin >> s;
    int start = 0, end = 0;
    while(true) {
        if(start >= s.size()) break;

        while(end < s.size() && s[end+1] != '+' && s[end+1] != '-') {
            end++;
        }

        string num_str = s.substr(start, end-start+1);
        int num;
        stringstream ssInt(num_str);
        ssInt >> num;

        operands.push_back(num);

        start = end+1; end = start;

        if(s[start] != '+' && s[start] != '-') {
            break;
        }
        else operators.push_back(s[start]);

        
        start++; end++;
    }

    int sum = operands[0]; int tmp = 0;
    for(int i=0; i<operators.size(); ++i){
        if(operators[i] == '-' && tmp == 0) {
            tmp += operands[i+1];
        } else if(operators[i] == '-' && tmp != 0) {
             sum -=tmp; tmp = operands[i+1]; 
        } else if(operators[i] == '+' && tmp == 0) {
            sum += operands[i+1];
        } else {
            tmp += operands[i+1];
        }
    }
 

    cout << sum-tmp << '\n';
    return 0;
}

아니 이 날 5문젠가 풀었는데 글 쓰다 접고 미루다 미루다 결국 한 문제 밖에 못썼네..ㅋㅋㅋㅋ

오늘은 2.18인데 생각해보니 요즘 백준을 안풀었었다… 시간 나면 꼭 백준을 다시 풀어야겠다.