[리트코드] 1111 - Maximum Nesting Depth of Two Valid Parentheses Strings

1111. Maximum Nesting Depth of Two Valid Parentheses Strings

Medium

---

A string is a valid parentheses string (denoted VPS) if and only if it consists of "(" and ")" characters only, and:

• It is the empty string, or
• It can be written as AB (A concatenated with B), where A and B are VPS's, or
• It can be written as (A), where A is a VPS.

We can similarly define the nesting depth depth(S) of any VPS S as follows:

• depth("") = 0
• depth(A + B) = max(depth(A), depth(B)), where A and B are VPS's
• depth("(" + A + ")") = 1 + depth(A), where A is a VPS.

For example, "", "()()", and "()(()())" are VPS's (with nesting depths 0, 1, and 2), and ")(" and "(()" are not VPS's.

Given a VPS seq, split it into two disjoint subsequences A and B, such that A and B are VPS's (and A.length + B.length = seq.length). The subsequences may not necessarily be contiguous.

For example, for the sequence 123456789, one possible split is:

• A = {1, 3, 5, 7, 9},

• B = {2, 4, 6, 8}.

This corresponds to the output [0, 1, 0, 1, 0, 1, 0, 1, 0]  where 0 indicates membership in A and 1 indicates membership in B.

Now choose any such A and B such that max(depth(A), depth(B)) is the minimum possible value.

Return an answer array (of length seq.length) that encodes such a choice of A and B:  answer[i] = 0 if seq[i] is part of A, else answer[i] = 1.  Note that even though multiple answers may exist, you may return any of them.

 

Example 1:

Input: seq = "(()())"
Output: [0,1,1,1,1,0]

Example 2:

Input: seq = "()(())()"
Output: [0,0,0,1,1,0,1,1]

 

Constraints:

• 1 <= seq.size <= 10000

분류

문자열, 스택, Bracket Sequences

---

문제 풀이

문제 분석

주어진 문자열 seq는 유효한 괄호 문자열(VPS)입니다. 이 문자열을 두 개의 부분 수열 A와 B로 분할해야 합니다.
조건은 다음과 같습니다.

• A와 B 모두 유효한 괄호 문자열(VPS)이어야 합니다.
• A와 B는 seq의 문자를 겹치지 않게 나누어 가져야 합니다(순서 유지).
• max(depth(A), depth(B)) 값이 최소가 되도록 분할해야 합니다.

출력은 seq의 각 문자가 A에 속하면 0, B에 속하면 1로 표시한 정수 배열입니다.

---

접근 방법

이 문제의 핵심 아이디어는 괄호의 깊이를 기준으로 홀짝(Parity)을 나누는 것입니다.

• VPS에서 여는 괄호 (는 깊이를 1 증가시키고, 닫는 괄호 )는 깊이를 1 감소시킵니다.
• 전체 문자열의 최대 깊이를 D라고 할 때, 두 그룹으로 나누어 각각의 최대 깊이를 약 D/2로 줄이는 것이 목표입니다.
• 현재 깊이가 홀수일 때와 짝수일 때를 서로 다른 그룹(0 또는 1)에 할당하면, 각 그룹 내에서는 깊이가 번갈아 가며 쌓이게 되어 최대 깊이가 절반 수준으로 줄어듭니다.
• 스택을 명시적으로 사용하지 않고, 현재 깊이(cnt) 변수 하나만으로 홀짝 판별이 가능하므로 O(1) 추가 공간(출력 제외)으로 해결할 수 있습니다.

---

구현 설명

1. 변수 초기화

cnt = 0
answer = []

• cnt: 현재 괄호의 중첩 깊이(열린 괄호의 개수 - 닫힌 괄호의 개수)를 추적합니다.
• answer: 결과를 저장할 리스트입니다.

2. 문자열 순회 및 그룹 할당

for x in seq:
    if x == "(":
        # 여는 괄호 처리
        ...
    else:
        # 닫는 괄호 처리
        ...

문자열의 각 문자를 순차적으로 보며 여는 괄호인지 닫는 괄호인지에 따라 로직을 분기합니다.

3. 여는 괄호 ( 처리 로직

if x == "(":
    if cnt % 2 == 1:
        answer.append(1)
    else:
        answer.append(0)
    cnt += 1

• 깊이 증가 전 현재 깊이(cnt)의 홀짝을 확인합니다.
• 현재 깊이가 홀수(cnt % 2 == 1)면 그룹 1에, 짝수면 그룹 0에 할당합니다.
• 할당 후 깊이를 1 증가시킵니다(cnt += 1).
• 이유: 여는 괄호는 현재 깊이에 속한 후 깊이를 늘리므로, 진입 시점의 깊이 기준으로 그룹을 결정해야 쌍이 맞는 닫는 괄호와 같은 그룹에 들어갑니다.

4. 닫는 괄호 ) 처리 로직

else:
    cnt -= 1
    if cnt % 2 == 1:
        answer.append(1)
    else:
        answer.append(0)

• 깊이 감소 후 현재 깊이(cnt)의 홀짝을 확인합니다.
• 현재 깊이가 홀수면 그룹 1, 짝수면 그룹 0에 할당합니다.
• 이유: 닫는 괄호는 자신이 닫는 여는 괄호의 깊이와 같아야 합니다. 여는 괄호는 깊이를 늘리기 전에 할당되었으므로, 닫는 괄호는 깊이를 줄인 후의 상태(즉, 해당 여는 괄호가 할당되었던 시점의 깊이)와 홀짝이 일치해야 같은 그룹이 됩니다.

---

⏱복잡도 분석

• 시간 복잡도: O(N)

  • seq의 길이 N만큼 단 한 번 순회하며 각 문자에 대해 O(1) 연산(홀짝 판별, 리스트 추가)만 수행합니다.

• 공간 복잡도: O(N)

  • 결과를 저장하는 answer 리스트의 크기가 N이므로 O(N)입니다.
  • 추가 변수(cnt, 루프 변수 등)는 상수 공간만 사용하므로 출력 공간을 제외하면 O(1)입니다.

---

핵심 포인트

1. 깊이의 홀짝(Parity) 활용: 최대 깊이를 절반으로 줄이기 위해 현재 중첩 깊이가 홀수인지 짝수인지에 따라 두 그룹으로 분배합니다.
2. 여는 괄호와 닫는 괄호의 시점 차이: 여는 괄호는 깊이 증가 전, 닫는 괄호는 깊이 감소 후의 홀짝을 기준으로 그룹을 결정해야 짝이 맞는 괄호가 같은 그룹에 속하게 됩니다.
3. 스택 없이 카운터만으로 해결: 유효한 괄호 문자열이 보장되므로 스택 자료구조 없이 단순 정수 카운터(cnt)만으로 현재 깊이를 정확히 추적할 수 있습니다.

풀이 코드

class Solution:
    def maxDepthAfterSplit(self, seq: str) -> list[int]:
        cnt = 0
        answer = []
        for x in seq:
            if x == "(":
                if cnt % 2 == 1:
                    answer.append(1)
                else:
                    answer.append(0)
                cnt += 1
            else:
                cnt -= 1
                if cnt % 2 == 1:
                    answer.append(1)
                else:
                    answer.append(0)
     
        return answer