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

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

🥈실버 2

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

1541번: 잃어버린 괄호

---

접근

1. -가 나타나기 전까지는 모든 값을 그냥 더해두고, - 이후의 숫자들은 모두 뺄셈처리 한다.

 

괄호를 한번 친다고 가정할 때, - 이후에 모든 값을 괄호로 묶는 것이 가장 최솟값이 나오는 방법이기 때문이다.

55-50+40 -> 55-(50+40) -> 55 - 50 - 40

 

해결방법은 찾았으나 구현을 어떻게 할지가 고민이었다.

 

1. 입력 받은 string 변수에서 어떻게 정수를 뽑아내야 할까?

 

각 항의 정수는 최대 다섯자리까지 올 수 있었다. 예제 입력중에 00009라는 것을 보고 반복문을 돌리다가 +나 -가 아니면 전부 string 더하기 연산으로 합쳐 놓고 stoi 메서드를 통해 정수로 바꾸는 아이디어를 생각할 수 있었다.

 

string으로 입력 값을 받는다.

반복문을 돌면서 정수를 뽑아낼 string 변수 tmp를 선언하고, 연산자가 나올때까지 tmp에 하나씩 추가한다.

연산자가 나오면 tmp값을 stoi 메서드를 통해 정수로 교체하고 정답으로 출력할 변수에 값을 더한다.

 

 

2. -연산을 어떻게 해야할까?

 

55+40-20+10

위와 같은 입력값을 가정한다.

정답으로 출력할 변수 int ans = 0에 tmp에서 가져온 정수를 더하거나 빼주어야 한다. ( ans += stoi(tmp) or ans -= stoi(tmp) )

위의 로직에 따르면 연산자가 나타날 때 해당 연산을 수행하므로,

반복문 순회중에 55+에서 ans에 55가 더해질 것이다.

 

하지만 이대로 갔을 때, 55+40-에서는 

새로 tmp에 들어온 40이 ans의 값에서 뺄셈처리가 된다.

의도했던 계산은 55+40-(20+10) -> 55+40-20-10과 같이 되어야 하는데 40이 더해지지 않고 뺄셈처리가 되는 문제가 발생한 것이다.

 

따라서 반복문에서 -가 최초로 탐색되었을 때는 현재 tmp에 있는 값을 ans에 더할 수 있도록 해야하고, 다음 정수 연산에서는 무조건 ans에 tmp값을 뺄셈처리 할 수 있도록 코드를 작성해야 한다.

 

isMinus라는 bool함수를 추가해서 처음 나왔을때 true로 만들고, 이후에 어떤 연산자가 나타나든 ans에 -tmp 연산을 추가한다.

 

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
  string input;
  cin >> input;
  string tmp;
  int ans = 0;
  bool isMinus = false;
  
  for (int i = 0; i <= input.size(); i++) {
    if (input[i] == '+' || input[i] == '-' || i == input.size()) { // 연산자 혹은 마지막 일 경우. 
      if (isMinus) ans -= stoi(tmp);  // - 이후에 들어온 모든 정수는 빼줘야 함
      else ans += stoi(tmp); // -가 처음 들어왔을 경우 그 앞에 있었던 정수는 더해줘야함
      tmp = ""; // 새로운 정수를 받기 위해 초기화
    }

    else {  // 일반 정수가 들어올 경우 tmp에 string 형태로 저장.
      tmp += input[i];
    }

    if (input[i] == '-') {  // -가 들어오면 그 다음에 들어올 모든 정수는 빼주어야 함.
      isMinus = true;
    }
  }
  
  cout << ans;

  return 0;
}