[BOJ] 1541. 잃어버린 괄호

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

1541번: 잃어버린 괄호

부호는 +와 -만 있고 값을 최소로 만들면 되므로 - 이후의 값들은 모두 괄호로 적절히 묶어서 -로 만들어 주면 된다. 

 

예를 들어 문제에 나온 예시인 55-50+40의 경우 55-(50+40) 이런 식으로 만들어줄 수 있다.

55-50+40-10 인 경우에는 55-(50+40)-10 이런 식으로 묶어준다고 생각하면 되므로 그냥 - 이후의 값들은 모두 음수 값으로 처리해준다.

 

음수 값으로 바꾸기 위해서 나는 flag라는 변수에 처음에 1을 넣어놓고 -가 나오기 전까지는 숫자가 들어올 때마다 flag를 곱해줬다. 그리고 - 부호가 들어오면 flag를 -1로 만들어서 더해지는 숫자가 마이너스 값이 되도록 했다.

 

 

 

구체적으로는 입력으로 들어오는 문자열의 각 문자에 대해서

+인 경우 / -인 경우 / 그 외의 경우(숫자)로 나눠서 각각 처리해주었다.

 

먼저 숫자인 경우에는 num 변수에 숫자를 저장해놨다가 +나 -가 나와서 숫자가 끝나면 num을 최종 값인 ans 변수에 더해주었다. 숫자가 연속으로 나올 수 있기 때문에 이전에 저장된 수에 10을 곱해준 후에 현재 문자를 숫자로 바꿔서 더해준다.

 

 55-50+40

문제의 예시를 다시 보면

5가 나오면 먼저 num에 5가 저장된다. 처음에 num에는 0이 저장되어 있으므로 10을 곱해주는 것은 상관없다.

그다음에 또 5가 들어오면 기존에 있던 5에 10을 곱해줘서 50으로 만들어주고 새로 들어온 5를 곱해준다.

그리고 -가 나오면 num에 있는 55를 ans에 더해준다. 뒤의 50과 40도 같은 방법으로 만들 수 있다.

 

 

+인 경우는 그냥 이전까지의 숫자(num)를 ans에 더해주고 num을 초기화해주면 된다.

 

-인 경우에는 위의 설명처럼 flag를 -1로 바꿔준다. 그리고 +와 마찬가지로 앞에서 숫자가 끝났으므로, 최종 값(ans)에 이전까지의 숫자(num)를 더해준다. 

 

#include<iostream>
#include <string>
using namespace std;
 
int arr[1000];
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    string s;
    cin >> s;
 
    int num = 0;
    int ans = 0;
    int flag = 1;
 
    for (char c : s) {
        if (c == '+') {
            //+가 나온 경우 숫자가 끝난 것이므로 num을 ans에 더해준 후 에 num을 0으로 초기화
            ans += num;
            num = 0;
        }
        else if (c == '-') {
            //- 인 경우 flag를 -1로 바꿔주고 이전까지의 num을 ans에 더해준다.
            //flag는 이후로 계속 -1 을 유지한다.
            flag = -1;
            ans += num;
 
            //더해줬으므로 num은 다시 0으로 초기화
            num = 0;
        }
        else {
            //숫자인 경우 num에 저장
            num = num * 10 + (c - '0')*flag;
        }
    }
 
    //마지막 숫자를 더해준다.
    ans += num;
 
    cout << ans << '\n';
 
    return 0;
}