C++의 최소 대괄호 추가

<시간/>

'(' 및 ')'만 포함하는 문자열 s가 있다고 가정하고 문자열을 균형 있게 만들기 위해 삽입할 수 있는 최소 괄호 수를 찾아야 합니다.

따라서 입력이 "(()))("와 같으면 출력은 "(()))("와 같이 2가 되며 "((()))()"와 같이 균형을 이룰 수 있습니다.

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

:=0, cnt :=0
initialize i :=0의 경우, i
- s[i]가 '('와 같으면 -
  - (o 1씩 증가)
- 그렇지 않으면
  - o가 0이 아닌 경우 -
    - (o를 1만큼 감소)
  - 그렇지 않으면
    - (cnt를 1씩 증가)
cnt + o를 반환

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

예시

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int solve(string s) {
      int o = 0;
      int cnt = 0;
      for(int i = 0; i < s.size(); i++){
         if(s[i] == '('){
            o++;
         } else {
            if(o)
               o--;
            else
               cnt++;
         }
      }
      return cnt + o;
   }
};
int main(){
   Solution ob;
   cout << (ob.solve("(()))("));
}

입력

Input:
"(()))("