[C++]1541번: 잃어버린 괄호

요약

• 위 조건에 맞는 문자열 자르기 - 정규 표현식 사용
• 덧셈의 합이 최소가 되기 위한 괄호의 조건 파악하여 매커니즘 구현

풀이과정

1. 정규표현식으로 문자열 정제하기

정규표현식

문제는 55-50+40과 같은 형태를 띄고 있다.

추후 내가 생각한 방식으로 문제를 풀기 위해, 55-50+40과 같은 문자열이 주어지만 55, -50, 40 으로 문자열을 분리하길 원했다.

이를 위해 정규표현식을 사용했다.

내가 추출하고자 하는 패턴은 다음과 같다.

 -로 시작할수도 있다.
숫자로 구성되며 1~5자리이다.

이를 위한 정규표현식은 /[-]?\d{1,5}/g 이다.

https://regexr.com/

[-]?	[-]	- '하나'
	?	해당 token이 1 또는 0 하나 나올수도(1) 안나올수도(0)
\d{1,5}	\d	digit (0-9)
	{1,5}	해당 token이 1~5개 나옴

위 정규표현식을 분석하면 위와 같다.

 

int로 vector에 저장하기

매칭되는 것 하나만 찾고 마는 것이 아니라, 주어진 문자열에서 정규표현식을 만족하는 모든 매칭값을 저장해야 한다.

이를 위해 sregex_iterator를 이용한다. 

반복자이기 때문에 매칭되는 모든 string을 반복자를 통해 접근할 수 있다.

기본형이 string이 아니기 때문에 *sregex_iterator로 애초에 start를 선언해주는 방법과, ->str()을 통해 string 값에 접근하는 방법이 있다.

 

int값으로 저장해야 하니 stoi를 이용한다.

    auto start = sregex_iterator(str.begin(), str.end(), re);
    auto end = sregex_iterator();

    while(start != end) {
        numvec.push_back(stoi(start->str()));
        ++start;
    }

잘 저장된 모습

2. 합 최소로 하기 위한 괄호 조건 고려하기

그냥 직관적으로 생각해보면,

모든 항이 덧셈으로 구성된 경우 괄호를 어떻게 치든 값의 변화를 이끌어내지 못한다.

 항에 뺄셈이 존재하는 경우, 이 빼는 값을 최대한 크게 만들어야 전체 연산의 최소값이 나오게 될 것이다.

예시인 55-50+40의 경우, 55 - (50+40) 을 통해 빼는 값을 최대한 크게 만들어야 최소값인 -35이 나오듯이

 

a-b+c+d-e+f-g 의 경우

a - ( b + c + d ) - ( e + f ) - g

이 되게끔 괄호를 쳐줘야 한다.

 

나는 뺄셈이 이전에 나왔는지 전역적으로 알아내기 위한 minusExist와

뺄셈 이후 축적된 값인 acc를 통해 저장된 값에 대해 양수/음수로 나누어 매커니즘을 짜 봤다.

    bool minusExist = false;
    int acc = 0;
    for(int item : numvec) {
        if(minusExist) {    //이전에 음수가 나왔음
            if(item >= 0) {
                acc += item;
            } else {    //음수가 또 나옴 : 축적된 acc값을 answer에 반영하고 acc 초기화
                answer -= acc;
                acc = abs(item);
            }
        } else {
            if(item >= 0) {
                answer += item;
            } else {
                minusExist = true;
                acc = abs(item);
            }

        }
    }
    answer -= acc;

코드

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

int main() {
    #ifdef LOCAL
    freopen("input.txt","r",stdin);
    #endif
    cin.tie(0) -> sync_with_stdio(0);

    string str = "";
    int answer = 0;
    vector<int> numvec;
    getline(cin,str);

    regex re("[-]?\\d{1,5}");   //regex 정의 : 앞에 -가 붙을수도 있으며 digit이 1~5자리인 패턴의 값

    auto start = sregex_iterator(str.begin(), str.end(), re);
    auto end = sregex_iterator();

    while(start != end) {
        numvec.push_back(stoi(start->str()));
        ++start;
    }


    bool minusExist = false;
    int acc = 0;
    for(int item : numvec) {
        if(minusExist) {    //이전에 음수가 나왔음
            if(item >= 0) {
                acc += item;
            } else {    //음수가 또 나옴 : 축적된 acc값을 answer에 반영하고 acc 초기화
                answer -= acc;
                acc = abs(item);
            }
        } else {
            if(item >= 0) {
                answer += item;
            } else {
                minusExist = true;
                acc = abs(item);
            }

        }
    }
    answer -= acc;

    cout << answer << endl;  

    
}

다른 사람의 풀이

문자열 정제하는 방법이 쉬운 편이라 직접 +, -에 대해 처리해주는 방식으로 하는 사람들이 많았다.

굳이 정규표현식을 안써도 쉬운 문제라서...

    string temp = "";
    for(char c : str) {
        if(c != '+') {
            if(c == '-') {
            numvec.push_back(stoi(temp));
            temp = "";  
            }
            temp += c;
        } else {
            numvec.push_back(stoi(temp));
            temp = "";
        }
    }
    numvec.push_back(stoi(temp));

위의 정규표현식 대신 이렇게 직접 분리해주는 방식도 짜봤다.

최소값 만드는 방법은 다른사람들 역시 동일했다.

다만, 더 간단하게 -가 한번이라도 나오면 뒤에 모든 값을 answer에서 빼는 방식도 있었다.

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

int main() {
    #ifdef LOCAL
    freopen("input.txt","r",stdin);
    #endif
    cin.tie(0) -> sync_with_stdio(0);

    string str = "";
    int answer = 0;
    vector<int> numvec;
    cin >> str;
    str += '\n';

    string temp = "";
    bool minusExist = false;
    int acc = 0;

    for(char c : str) {
        if(minusExist) {    //모두 answer에서 뺌
            if(c == '+' || c == '-' || c == '\n') {
                answer -= stoi(temp);
                temp = "";
            } else {
                temp += c;
            }  
        } else {
            if(c == '+' || c == '-' || c == '\n') {
                answer += stoi(temp);
                temp = "";
                if(c == '-')
                    minusExist = true;
            } else {
                temp += c;
            } 

        }
    }

    cout << answer << endl;   
}

아예 다시 짜봤다. 문자 분류 + 합구하기까지 한번에 한다.

그리고 \n을 마지막에 추가해줘서 마지막 값도 누락되지 않게 하는 걸 깔끔하게 반복문 안에 정리해봤다.