[백준] 잃어버린 괄호 (C++)

 

문제 URL:

www.acmicpc.net/problem/1541

1541번: 잃어버린 괄호

 

다음 문제는 주어진 식에 괄호를 적절히 쳐서 식의 값을 최소로 만드는 문제로,

벡터에 숫자들을 저장하고 그 숫자들을 이용해 계산을 하는 방식으로 문제를 풀었다.

 

이 문제에서 (-) 부호 뒤에 양수가 있다면 괄호로 뒤이어 오는 양수들을 모두 묶어 한 번에 음수로 만들어 주어야

주어진 식이 최소가 될 수 있다.

 

위의 원리를 이용해 코드를 작성하였는데 과정은 다음과 같다.

 

• 문자열 s를 입력받고 문자열의 각 요소들을 +, -, 숫자를 기준으로 나눈다.
• 문자열의 요소가 숫자일 때는 문자열 변수 temp를 사용하여 숫자를 저장해준다.
  여기서 temp에 저장된 값은 문자열이기 때문에 stoi() 함수를 이용하여 숫자로 변환하는 과정이 필요하다.
• +일 때와 -일 때는 각각 변수 x를 이용하여 부호를 설정해준 뒤, 이 x를 temp 숫자와 곱하여 벡터에 저장(push_back)한다.
  
• 모든 숫자를 벡터에 저장했다면 앞서 설명한 원리와 같이 부호를 조건으로 계산을 진행한다.

 

+) 이 문제에서 개인적으로 어려웠던 점은 여러 자리 숫자는 어떻게 저장해야 해야 하는가였다.

(후에 문자열 변수 temp를 이용하면 된다는 걸 검색을 통해 알아냈다..)

---

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

int main()
{
    vector<int> v;
    int n, x=1, a, count=0, sum=0;
    string s;
    string temp = "";
    cin >> s;
    
    for(int i=0; i<s.size(); i++)
    {
        if(s[i]=='+')
        {
            v.push_back(x*stoi(temp));
            x=1;
            temp = "";
        }
        else if(s[i]=='-')
        {
            v.push_back(x*stoi(temp));
            x=-1;
            temp = "";
        }
        else
            temp += s[i];
    } 
    v.push_back(x*stoi(temp));
    
    while(v.size()!=0)
    {
        a = v.back();
        v.pop_back();
        if(a<0)
        {
            if(count!=0)
            {
                sum = sum+a-count;
                count = 0;
            }
            else
                sum += a;
        }
        else
            count += a;
    }
    
    sum += count;
    cout << sum;
}