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

#문제

1541번: 잃어버린 괄호

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

1541번: 잃어버린 괄호

 

---

#접근방법

숫자, '+', '-' 를 분리하고 '+'연산부터 한 다음 '-'연산을 해주었다. 그리디 알고리즘으로 접근하였다.

반응형

---

#풀이

#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<int> v;

int main(){
    int s = 0;
    int x;
    int ans = 0;
    string a;

    cin >> a;

    for(int i=1;i<a.size();i++){
        if(a[i]=='-' || a[i]=='+'){
            x = stoi(a.substr(s,i-s));

            if(x>=0 && v.size()>0 && v.back()<0){
                v.back() -= x;
            }
            else v.push_back(x);

            s = i;
        }
    }
    x = stoi(a.substr(s,a.size()-s));
    if(x>=0 && v.size()>0 && v.back()<0){
        v.back() -= x;
    }
    else v.push_back(x);

    for(int i=0;i<v.size();i++)
        ans += v[i];

    printf("%d",ans);

    return 0;
}

 

위 문제에서 식이 가장 최소값이 되도록 하는 경우는 '+'연산부터 한 다음 '-'연산을 실행시켜주면 된다.

 

먼저 string 자료형으로 식 전체를 입력받는다.

 

1 ~ a.size() 만큼 반복문을 돌면서 숫자를 분리해준다. a[i]가 '+' 또는 '-'일 경우에 변수 x에 stoi(a.substr(s,i-s))값을 저장해준다. stoi 함수는 string 자료형을 int 자료형으로 바꾸어주는 함수이다. 그리고 substr은 a.substr(시작 위치, 개수)의 형식으로 string 자료형에서 시작 위치에서 오른쪽으로 몇 칸까지 추출해주는 함수이다.

 

이렇게 되면 식에서 숫자가 추출이 되고 vector 자료구조에 저장시켜준다. 이 때, 최근에 추출한 값 중 음수이면서 현재 추출한 값이 양수이면 v.back() -= x으로 '+'연산을 해준다.

 

반복문이 끝나면 식에서 맨 뒤에 있는 숫자가 추출이 안되므로 예외처리로 맨 뒤에 있는 숫자도 추출하여 vector에 저장해준다.

 

그렇게 되면 vector 자료구조에 '+'연산을 먼저 한 값을이 있을 것이다. 이 값을을 모두 더해서 출력하면 정답이다.

 

---

#성능

---

#정리

식이 최소가 되기위해 '+'연산을 먼저하고 '-'연산을 나중에 한다는 사실,

 

stoi, substr 함수를 알고 있고 이를 구현할 수 있는 능력이 있으면 쉽게 풀 수 있는 문제였다.