[Leetcode] 1111. Maximum Nesting Depth of Two Valid Parentheses Strings (C++)

https://leetcode.com/problems/maximum-nesting-depth-of-two-valid-parentheses-strings/

Maximum Nesting Depth of Two Valid Parentheses Strings - LeetCode

[풀이] Greedy

 

문제해석이 어려운 문제.

결론적으로 어떤 VPS를 A,B 두 VPS로 나누는 문제. 이 때 depth(A,B)가 최소가 되도록 나누어야 한다.

처음엔 당연히 연속되는 괄호들로 나눠야 한다고 생각했는데

예제를 보니 ()(())() 와 같이 나눠도 된다.

depth를 가장 작게 하려면 겹치는 괄호를 최소한으로 만들어야 한다.그러려면 stack에 여는 괄호를 넣을 때 0,1,0,1 이런식으로 차례대로 넣어주면 된다.닫는 괄호는 여는 괄호와 같은 그룹에 들어가야 하므로 top과 같은 값으로 설정해주면 된다.

 

 

#include <stack>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
 
class Solution {
public:
    vector<int> maxDepthAfterSplit(string seq) {
        vector<int> ans(seq.size());
        stack<int> a;
        for (int i = 0; i < seq.size(); i++) {
            char c = seq[i];
 
            if (c == '(') {
                if (a.empty()) a.push(0);
                else a.push(1 - a.top());
                ans[i] = a.top();
            }
            else {
                ans[i] = a.top();
                a.pop();
            }
        }
        return ans;
    }
};

https://github.com/has2/Algorithm/blob/master/leetcode/1111.%20Maximum%20Nesting%20Depth%20of%20Two%20Valid%20Parentheses%20Strings.cpp