[C++] BAEKJOON 1541 잃어버린 괄호

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

1541번: 잃어버린 괄호

그리디 알고리즘 을 이용해서 문제를 해결하였습니다.

식의 값이 최소가 되기 위해서는 - 가 나온 순간 괄호를 쳐서 그 이후에 나오는 + 들을 전부 음수로 바꿔주면 됩니다. 값을 담는 벡터와 부호를 담는 벡터를 선언하여 들어오는 값을 나누어 넣어준 후 하나씩 꺼내보면서 위의 과정을 실행하였습니다.

#include <iostream>
#include <vector>

using namespace std;

int main(int argc, const char * argv[]) {
    
    string input;
    cin >> input;
    
    vector <int> numV;
    // + : 1, - : -1
    vector <int> signV;
    int answer = 0;
    
    bool minus = false;
    signV.push_back(1);
    
    int num = 0;
    
    for (int i=0;i<input.size();i++){
        if (input[i] == '+' || input[i] == '-'){
            if (input[i] == '+') signV.push_back(1);
            else signV.push_back(-1);
            numV.push_back(num);
            num = 0;
        }
        else{
            num = num * 10 + input[i]-'0';
        }
    }
    numV.push_back(num);
    
    for (int i=0;i<numV.size();i++){
        if (signV[i] == -1) minus = true;
        if (minus) answer -= numV[i];
        else answer += numV[i];
    }
    
    cout << answer << "\n";
    
    return 0;
}

 

string to int

전체 입력은 문자열로 들어오고 그 중에서 중간에 정수들을 뽑아내야 하기 때문에 string 을 int 로 바꿔줄 상황이 생깁니다. 처음에는 string -> char * -> int 과정을 거치며 정의되어 있는 메소드들을 사용했습니다.

string numStr = "";
for (int i=0;i<input.size();i++){
  if (input[i] == '+' || input[i] == '-'){
    if (input[i] == '+') signV.push_back(1);
    else signV.push_back(-1);
    // c_str : string -> char *
    // atoi :  char * -> int,  <cstdlib> 안에 있음
    int num = atoi(numStr.c_str());
    numV.push_back(num);
    num = 0;
  }
  else{
    numStr += input[i];
  }
}

이보다는 위의 방법이 더 직관적이고 다른 라이브러리를 불러올 필요도 없이 더 편해 방법을 바꾸었습니다.