[백준] 1541번 잃어버린 괄호 해설 및 풀이 (C++)

문제

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.
그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.
괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

입력

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.

출력

첫째 줄에 정답을 출력한다.

[ 문제보러 가기 ]

풀이 도출 과정

• 구해야 하는 답을 최소로 만들어야 한다.
• '-' 기호가 한 번 이라도 나올 시 그 뒤에 있는 정수들은 뺄셈 처리 한다.

시간 복잡도

• for문으로 n번 순회 : O(n)

#include <iostream>
#include <string>
using namespace std;
int main() {
  string str;
  string num = "";
  cin >> str;
  bool isMinus = false;
  int result = 0;
  for (int i = 0; i <= str.length(); i++) {
      if (str[i] == '-' || str[i] == '+' || i == str.length()) {
      		// isMinus가 true일 시에, 그 뒤에 나온 정수들을 뺄셈 처리
          if (isMinus) {
              result -= stoi(num);
              num = "";
          }
          // isMinus가 false일 시에(마이너스 기호가 아직 안나왔다는 뜻), 현재 정수까지 덧셈 처리
          else {
              result += stoi(num);
              num = "";
          }
      }
      // '-'와 '+' 기호가 나오기전까지는 string형태의 num을 이어준다.
      else {
          num += str[i];
      }

			  // 한 번 이라도 '-'기호가 나왔다면, isMinus을 true
      if (str[i] == '-') {
          isMinus = true;
      }
  }

  cout << result << '\n';
}