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

코딩테스트/백준

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

윤깡패 2023. 6. 9. 19:42

문제

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

1541번: 잃어버린 괄호

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

www.acmicpc.net

풀이

그리디(Greedy) 알고리즘

그리디(Greedy) 알고리즘 현재 상태에서 볼 수 있는 선택지 중에 최선의 선택을 하는 알고리즘 + 구현하기 쉽다. + 시간 복잡도가 우수하다. - 항상 최적의 해를 보장하지 못한다. 그리디 알고리즘

soobin0821.tistory.com

코드

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

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  string str;
  cin >> str;

  vector<int> minus_numbers;
  vector<int> plus_numbers;
  string num;
  int minus_index = -1;

  for(int i = 0; i < str.length(); i++)
  {
    if(str[i] == '-')
    {
      minus_index = i;
      break;
    }
    else if(str[i] == '+')
    {
      plus_numbers.push_back(stoi(num));
      num.erase();
    }
    else
    {
      num += str[i];
    }
  }
  plus_numbers.push_back(stoi(num));
  num.erase();

  if(minus_index > -1)
  {
    for(int i = minus_index + 1; i < str.length(); i++)
    {
      if(str[i] == '-' || str[i] == '+')
      {
        minus_numbers.push_back(stoi(num));
        num.erase();
      }
      else
      {
        num += str[i];
      }
    }
    minus_numbers.push_back(stoi(num));
  }

  int result = 0;
  for(int i = 0; i < plus_numbers.size(); i++)
  {
    result += plus_numbers[i];
  }
  for(int i = 0; i < minus_numbers.size(); i++)
  {
    result -= minus_numbers[i];
  }

  cout << result;

  return 0;
}

728x90