[Leetcode]1111. Maximum Nesting Depth of Two Valid(x)

1. problem :

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

 

2. solution 1 :

class Solution {
    public int[] maxDepthAfterSplit(String seq) {
        int n = seq.length () ,s1 =0, s2 = 0;
        int[] ans = new int [n] ;
        for ( int i = 0 ; i < n ; i ++ ){
            if ( seq.charAt (i) =='(' ){
                if ( s1 <= s2){
                    s1 ++;
                    ans[i] = 0;
                }
                else {
                    s2 ++;
                    ans [i] = 1 ;
                }
            }
            else {
                if ( s1 > s2){
                    s1 -- ;
                    ans [i] = 0 ;
                }
                else {
                    s2 --;
                    ans [i] = 1 ;
                }
            }
        }
        return ans ;
    }
}

이 solution은 다른 사람이 작성한 solution이다. s1, s2를 변수로 두었다. 이 변수는 두 string의 depth를 저장하는 변수다. 

만약 '('를 만나게 되었을 때, s1 <= s2라면 s1을 +1 해준다. 그리고 ans [i] = 0으로 설정한다. 만약 s1 > s2라면 s2 +1 해준다. 그리고 ans [i] =1을 설정해 준다. 

만약 ')'를 만나게 되었을 때는, s1과 s2의 크기를 비교해 s1이 크다면 (depth가 깊다면) s1을 줄여준다. 그리고, ans [i] = 0을 설정해 준다. 반대의 경우도 마찬가지다. 

예를 들어, "((()))"이라는 str이 있다면, 번갈아가며, 할당한다는 이야기다. 그래야 각각의 string의 depth를 minimize 할 수 있으니깐 말이다. https://leetcode.com/problems/maximum-nesting-depth-of-two-valid-parentheses-strings/solutions/4973161/100-with-stack-without-stack-java-c-all-in-one-code-with-easy-e xplanation 

이 링크에 그 사람의 solution에 대한 설명이 잘 기록되어 있다. 

 

3. solution 2 :

class Solution {
    public int[] maxDepthAfterSplit(String seq) {
        int n = seq.length();
        int[] ans = new int[n];
        int depth = 0;
        for (int i = 0; i < n; i++) {
            char c = seq.charAt(i);
            if (c == '(') {
                ans[i] = depth % 2;
                depth++;
            } else {
                depth--;
                ans[i] = depth % 2;
            }
        }
        return ans;
    }
}

이 solution은 chatgpt 4o가 짜준 코드이다. 여기서는 depth++와 depth--를 수행하는 시점이 중요한 포인트다. 

'('를 만났을 때는, ans [i] = dpeth %2를 설정한 다음 depth ++;을 해준다. 하지만 , ')'를 만났을 때는, depth--를 해준 다음, ans [i] = depth % 2;를 설정해 준다. 외우자.