[1541] 잃어버린 괄호

---

 

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

1541번: 잃어버린 괄호

 

---

 

수식의 값을 최소로 만들기 위해서는, '-'와 '-' 사이에 있는 숫자들을 모두 괄호 안에 집어넣으면 된다!

ex) 1+2-3+4+5-6+7 인 경우,

1+2-(3+4+5)-(6+7) 이렇게 괄호를 치면 된다.

이때, 연산자가 '-'인 경우에만 continue를 해주면 되는 이유는 

tmp = 55 또는 tmp = +55 인 경우에 stoi(tmp)는 똑같이 양수 55이기 때문이다. 

 

이 문제의 중요한 포인트는 3가지이다.

1. 처음에 수식을 입력받을 때 int형이나 char형의 배열이 아닌, string 으로 입력받는 것이다!!!!

그러기 위해서는 헤더에 #inlcude <string> 을 해줘야 한다.

수식으로 '55-50+40'을 입력받으면

expr[0]=5, expr[1]=5, expr[2]=- ... 이와 같은 식으로 저장이 된다.

2. 숫자를 더하기 위한 임시 공간으로 tmp 변수를 선언했는데, 이떄 tmp의 자료형 역시 string이다!

tmp+=expr[0] -> tmp = 5

tmp+=expr[1] -> tmp = 55

이런식으로 입력하기 위해서!

3. answer에 tmp를 저장하고 나면 tmp를 초기화 해줘야 하는데, 이떄 tmp = ""와 같이 초기화 해주면 된다.

 

---

 

🔎 해결 방법 

1. 수식을 string으로 입력받는다.

2. 연산자이면서 minus가 true인 경우, answer에 -stoi(tmp)을 더해준다.

연산자이면서 minus가 false인 경우, answer에 +stoi(tmp)을 더해준다.

if문을 나오면서 tmp을 ""으로 초기화해준다.

3. 연산자가 '-'인 경우, minus을 true로 만들어준다.

tmp에는 숫자만 더해줘야 하므로, continue한다.

4. 수식인 경우 tmp에 계속 더해준다.

 

---

 

💡 내 코드(C++) 

// [1541] 잃어버린 괄호
// https://www.acmicpc.net/problem/1541
// 그리디 알고리즘

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

int main(void)
{
    string tmp, expr;
    int answer = 0;
    bool minus = false;
    cin >> expr; // 식 입력
    for (int i = 0; i <= expr.length(); i++) {
        // 연산자인 경우
        if ((expr[i] == '-') || (expr[i] == '+') || (expr[i] == '\0')) {
            if (minus == true)
                answer -= stoi(tmp);
            else
                answer += stoi(tmp);
            tmp = "";
        }
        
        if (expr[i] == '-') {
            minus = true;
            continue;
        }
        
        // 연산자가 아닌 경우(숫자인 경우)
        tmp += expr[i];
    }
    printf("%d\n", answer);
}