[BOJ-1541][C++] 잃어버린 괄호

문제

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.

그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.

괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

 

입력

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.

 

출력

첫째 줄에 정답을 출력한다.

 

예제 입력 1

55-50+40

 

예제 출력 1

-35

 

예제 입력 2 

10+20+30+40

 

예제 출력 2

100

 

예제 입력 3

00009-00009

 

예제 출력 3

0

 

알고리즘 분류

• 수학
• 문자열
• 그리디 알고리즘
• 파싱

 

문제 출처

https://www.acmicpc.net/problem/1541

1541번: 잃어버린 괄호

 

---

 

문제 해결 방법

• 입력된 식에서 특정한 위치에 괄호를 추가하여 연산 결과의 최솟값을 출력시키는 문제이다.
• 문제 해결을 위한 알고리즘은 다음과 같다.

1. 식을 넣은 문자열(@equation@)의 첫 번째 인덱스부터 마지막 인덱스까지 순회하면서, 숫자들을 벡터(@result@)에 넣는다. 단, @-@ 기호를 만날 경우, 그 뒤의 숫자들을 전부 음수로 바꿔준 후 벡터(@result@)에 넣어 준다.
2. 숫자들을 넣은 벡터의 총합(@sum@)을 구한 후, 출력시켜준다.

• 이 알고리즘을 코드로 작성해보면 다음과 같다.

int Solution(string eq) {
    int n;
    long long sum;
    bool isMinus;
    string num;
    vector<int> result;

    sum = 0;
    isMinus = false;
    for (int i = 0; i <= eq.size(); i++) {
        if (('0' <= eq[i]) && (eq[i] <= '9')) {
            num += eq[i];
        }
        else {
            n = (isMinus == true) ? (stoi(num) * -1) : stoi(num);    // 접근한 값이 -이면, isMinus의 값에 따라 결과 벡터에 넣을 값을 변화시켜 준다.
            if (eq[i] == '-') {
                isMinus = true;       
            }
            result.push_back(n);
            num.erase();
        }
    }

    for (auto i : result) {
        sum += i;
    }

    return sum;
}

 

예제를 통해 알고리즘 이해하기

• @예제 입력 1@을 통해 문제를 이해해보면 다음과 같다.

55-50+40

인덱스	0	1	2	3	4	5	6	7	8
	5	5	-	(5	0	+	4	0)	\0

• @-@ 뒤의 식에 괄호를 추가하면, 다음과 같은 연산을 할 수 있게 된다. 그 결과, 최솟값인 @-35@를 출력할 수 있다.

55-(50+40)

 

코드

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

string equation;

void Input() {
    cin >> equation;
}

int Solution(string eq) {
    int n;
    long long sum;
    bool isMinus;
    string num;
    vector<int> result;

    sum = 0;
    isMinus = false;
    for (int i = 0; i <= eq.size(); i++) {
        if (('0' <= eq[i]) && (eq[i] <= '9')) {
            num += eq[i];
        }
        else {
            n = (isMinus == true) ? (stoi(num) * -1) : stoi(num);    // 접근한 값이 -이면, isMinus의 값에 따라 결과 벡터에 넣을 값을 변화시켜 준다.
            if (eq[i] == '-') {
                isMinus = true;       
            }
            result.push_back(n);
            num.erase();
        }
    }

    for (auto i : result) {
        sum += i;
    }

    return sum;
}

void Output() {
    cout << Solution(equation) << '\n';
}

void Solve() {
    Input();
    Output();
}

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

    Solve();

    return 0;
}

 

채점 결과

 

참고

• [단계별로 풀어보기] > [그리디 알고리즘]
• 실버II