백준 1541 잃어버린 괄호

작성일 | In |

Problem : 잃어버린 괄호

유형 : 그리디

문제 해석

  • 괄호를 적절히 쳐서 식의 결과 값을 최소로 만든다.

문제 재해석

  • 등장하는 기호는 +와 - 밖에 없다.
  • 시작이 0으로 시작할 수 있다.
  • 괄호의 개수 제한은 없다.

해결 전략

  • 마이너스가 한번이라도 등장한 순간, 뒤에 모든 정수는 음수 처리가 가능하다.
    • 이후에 음수가 등장할 경우, 아무런 작업을 하지 않으면 된다.
    • 이후에 양수가 등장할 경우, 음수 연산전에 괄호로 묶으면 된다.
  • 그리디 문제이다.

구현, 설계

  • 정규식을 이용해 문제를 해결한다.
  • 음수인 부분까지 고려하여 -?[0-9]+ 로 정규식을 만든다.
  • 문자열에서 숫자를 파싱한다.
  • 음수가 한번이라도 등장하면 해당 연산을 포함한 이후 모든 연산은 감소로 진행한다.

디버깅

  • c++ 정규식을 너무 오랜만에 써서 sregex_iterator 등등 문법이 기억이 안났다.
  • 음수 이후의 숫자들은 모두 음수로 만들어 줄 때 음수에 마이너스를 취해 양수로 만드는 경우가 없게 해야 한다.
  • 생성자 증가 연산을 빼 먹었었다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
#include <regex>
using namespace std;

string str;

void Solve() {
    regex reg("-?[0-9]+");
    sregex_iterator it(str.begin(), str.end(), reg);
    sregex_iterator it_end;

    bool minus_flag = false;
    int sum = 0;

    while (it != it_end) {
        int num = stoi((*it).str());
        if (!minus_flag and num < 0) minus_flag = true;

        if (minus_flag) sum -= abs(num);
        else sum += num;

        it++;
    }
    cout << sum << "\n";
}

void Input() {
    cin >> str;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    //freopen("input.txt", "r", stdin);

    Input();
    Solve();

    return 0;
}

피드백

  • smatch 변수를 따로 두지 않고, 바로 str()으로 파싱이 가능하다.
  • 이번주는 무리고 다음주 중에 c++ 정규식 관련 정리글을 포스팅하며 복습해야겠다.
  • 역에 역을 취하여 의도치 않는 결과가 나오지는 않는지 확인하자