모든 작업 후 최소 스톤을 찾는 C++ 코드

<시간/>

n개의 문자가 있는 문자열 S가 있다고 가정합니다. 문자는 '+' 또는 '-'입니다. 돌 더미가 있습니다. n 번 우리는 더미에서 하나의 돌을 가져오거나 더미에 하나의 돌을 추가했습니다. 더미에서 하나의 돌을 가져오는 각 작업 전에 더미는 비어 있지 않았습니다. 우리는 이러한 작업을 수행한 후 더미에 있을 수 있는 최소한의 가능한 돌 수를 찾아야 합니다. i번째 연산에서 스톤을 취하면 S[i]는 "-"와 같고, 추가하면 S[i]는 "+"와 같습니다.

따라서 입력이 S ="++-++"와 같으면 출력은 3이 됩니다. 처음에 더미에 0개의 돌이 있었다면 작업을 수행한 후 돌의 수는 3과 같습니다.

단계

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n := size of S
for initialize i := 0, when i < n, update (increase i by 1), do:
   res := (if S[i] is same as '-', then maximum of res - 1 and 0,
otherwise res + 1)
return res

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
int solve(string S){
   int n = S.size(), res = 0;
   for (int i = 0; i < n; i++)
      res = (S[i] == '-') ? max(res - 1, 0) : res + 1;
   return res;
}
int main(){
   string S = "++-++";
   cout << solve(S) << endl;
}

입력

"++-++"