[백준] 1541번 : 잃어버린 괄호

문제

 

---

풀이

 

풀이는 간단한데, 코드 작성이 까다로울 수 있는 문제이다.

먼저 예제 입력1에 대해 괄호를 치면 어떻게 될까? 55-(50+40)이 될 것이다.

그렇다면 이번엔 55-50+40+10-45+22 뭐 이런식이 있다고 치자. 여기에 괄호를 치면 55-(50+40+10)-(45+22)가 될 것이다.

 

눈치챘겠지만, 마이너스를 기준으로 양옆에 괄호를 치면 최솟값이 나온다.

그럼 마이너스 하나하나 찾아서 괄호를 쳐야할까? 그런 귀찮은 짓을 할 이유는 없다.

55-(50+40+10)-(45+22) 이 식은 55-(50+40+10+45+22) 이렇게 바꾸어도 똑같은 식이다.

 

즉, 마이너스가 처음 등장하는 지점을 기준으로 A - B의 형태를 만들어 A, B의 식을 각각 더한뒤 그 둘을 빼주면 최솟값이 나온다.

---

소스코드

 

#include <iostream>
#include <string>
#include <vector>
#include <stack>

using namespace std;

int calc(string expression, int start, int end) {
    int sum = 0;
    vector<int> num_arr;
    stack<int> num_stack;

    for (int i = start; i <= end; i++) {
        if (expression[i] == '-' || expression[i] == '+' || i == end) { //op 또는 배열의 끝이면 스택에 쌓인 수를 빼서 가공
            int temp = 0;
            int mul = 1;
            while (!num_stack.empty()) {
                temp += (num_stack.top() * mul);
                num_stack.pop();
                mul *= 10;
            }
            num_arr.push_back(temp);
        } else //숫자를 스택에 넣어줌
            num_stack.push(expression[i] - '0');
    }
    for (int i = 0; i < num_arr.size(); i++) //배열에 쌓인 수를 모두 더함
        sum += num_arr[i];
    return sum;
}

int bracket(string expression) {
    int length = expression.size();
    int minus_point = 60;

    for (int i = 0; i < length; i++) {
        if (expression[i] == '-') { //마이너스가 처음 등장하면 그 기준으로 이전 식을 전부 더한 것과 이후 식을 전부 더한 것을 빼면 됨
            minus_point = i;
            break;
        }
    }
    if (minus_point == 60) //식에 마이너스가 없을 수도 있음
        return calc(expression, 0, length);
    else //마이너스를 기준으로 앞 뒤를 나누어 더하고 서로 빼줌
        return calc(expression, 0, minus_point) - calc(expression, minus_point + 1, length);
}

int main() {
    string expression;

    cin >> expression;
    cout << bracket(expression);
}

말했듯이 풀이법에 비해 코드가 긴편이다.

 

int bracket(string expression) {
    int length = expression.size();
    int minus_point = 60;

    for (int i = 0; i < length; i++) {
        if (expression[i] == '-') { //마이너스가 처음 등장하면 그 기준으로 이전 식을 전부 더한 것과 이후 식을 전부 더한 것을 빼면 됨
            minus_point = i;
            break;
        }
    }
    if (minus_point == 60) //식에 마이너스가 없을 수도 있음
        return calc(expression, 0, length);
    else //마이너스를 기준으로 앞 뒤를 나누어 더하고 서로 빼줌
        return calc(expression, 0, minus_point) - calc(expression, minus_point + 1, length);
}

bracket 함수에서는 처음으로 등장하는 마이너스의 위치를 찾는다.

입력으로 주어지는 식의 길이는 50이하라고 했으니 식에 마이너스가 있다면 minus_point 역시 그보다 작을 것이다.

 

마이너스를 찾지 못했다면 그 식은 플러스로만 이루어진 식이라는 뜻이니 식 전체에 대해 calc 함수를 실행하고,

마이너스를 찾았다면 그 지점을 기준으로 식을 둘로 나누어 각각에 대해 calc 함수를 실행한 뒤 그 결과를 빼준다.

 

int calc(string expression, int start, int end) {
    int sum = 0;
    vector<int> num_arr;
    stack<int> num_stack;

    for (int i = start; i <= end; i++) {
        if (expression[i] == '-' || expression[i] == '+' || i == end) { //op 또는 배열의 끝이면 스택에 쌓인 수를 빼서 가공
            int temp = 0;
            int mul = 1;
            while (!num_stack.empty()) {
                temp += (num_stack.top() * mul);
                num_stack.pop();
                mul *= 10;
            }
            num_arr.push_back(temp);
        } else //숫자를 스택에 넣어줌
            num_stack.push(expression[i] - '0');
    }
    for (int i = 0; i < num_arr.size(); i++) //배열에 쌓인 수를 모두 더함
        sum += num_arr[i];
    return sum;
}

calc 함수에서는 string으로 입력받은 식에서 숫자와 연산자를 구분해서 계산한다.

정수의 길이를 모르는 상황에서 정수의 입력이 끝났음을 알 수 있는 표식은 무엇이 있을까? 연산자와 식의 끝지점이다.

 

스택에 숫자 하나하나를 독립적으로 저장하다가 이런 표식을 만나면 스택에 들어온 수를 꺼내어 하나의 정수로 만든다.

이 정수들은 num_arr 배열에 쌓이게 되고 마지막에 배열안의 값을 전부 더해주면 된다.