[LeetCode] 1111. Maximum Nesting Depth of Two Valid Parentheses Strings

문제

---

A string is a valid parentheses string (denoted VPS) if and only if it consists of "(" and ")" characters only.
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).

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.

 

괄호들만 담긴 문자열seq가 주어졌을 때, 이를 최대 깊이가 가장 작게 두 개로 분리시키는 문제이다.

깊이는 괄호의 깊이로, "()"는 깊이가 1, "(())"는 깊이가 2, "(()()())"는 깊이가 2이다.

분리시킨다는 것은 연속될 필요가 없이 원하는 부분만 골라서 빼내면 된다.

 

예를 들면 "()(())()"가 주어졌을 때 아래 그림처럼 분리하면

 

 

 

 

 

최대 깊이가 1{ =max(A의 최대 깊이 1, B의 최대 깊이 1)   }이 되고, 이는 만들 수 있는 경우중 가장 작은 값이된다.

따라서 [0, 0, 0, 1, 1, 0, 1, 1]을 반환하면 된다. (0과 1로 A와 B를 구분하면 된다.)

여기서 최대 깊이가 1이되는 경우가 여럿 있지만, 전부 정답처리 된다.

 

---

 

풀이

---

아이디어

두 개로 분리하기 때문에, 아무리 잘 분리해도 seq최대깊이 = A최대깊이 + B최대깊이 가 된다.

따라서 seq최대깊이//2 가 되는 부분을 분리하면 잘 분리 될 것이다.

 

구현 방식은 두 가지가 떠올랐다.

1. 먼저 seq의 최대깊이를 구한 후, seq를 처음부터 살펴보며 seq최대깊이//2에 도달하는 부분을 기억했다가 마지막에 분리한다.

2. seq를 처음부터 살펴보며 깊이를 저장해 놨다가 마지막에 seq최대깊이{ =max(저장한 깊이)  }//2를 기준으로 분리한다.

 

1번 방식은 로직이 복잡해져 2번 방식을 사용했다.

 

코드

class Solution:
    def maxDepthAfterSplit(self, seq: str) -> List[int]:
        answer = []
        depth = 0
        for c in seq:
            # 깊어짐, 깊이 기억
            if c == "(": 
                depth += 1
                answer.append(depth)

            # 얕아짐, 깊이 기억
            else:
                answer.append(depth)
                depth -= 1

        # seq최대깊이//2를 기준으로 분리
        return list(map(lambda x: 0 if x<=max(answer)//2 else 1, answer))

 

정답이 되긴 했지만, 친구에게서 더 좋은 아이디어를 얻었다.

(((())))에서 깊이가 1, 2인 괄호를 분리시키나 1, 4를 분리시키나 같다는 것이다.

 

결국 어떤 기준을 통해 절반을 분리하기만 하면 됐다.

절반을 분리하기 좋은 기준은 홀짝으로, 깊이의 홀짝을 통해 분리하면 정답처리가 된다.

class Solution:
    def maxDepthAfterSplit(self, seq: str) -> List[int]:
        answer = []
        depth = 0
        for c in seq:
            # 깊어짐, 깊이 기억
            if c == "(": 
                depth += 1
                answer.append(depth)

            # 얕아짐, 깊이 기억
            else:
                answer.append(depth)
                depth -= 1

        # 깊이의 홀짝을 기준으로 분리
        return list(map(lambda x: x%2, answer))

 

코드가 더 간결해지고 Runtime 속도가 빨라졌다.

1000ms -> 30ms

---

 

후기

---

난이도

문제 이해가 어려웠다.

문제가 영어로 되어 있고 예시가 빈약해서인 것도 있지만, 꽤나 복잡한 문제였다고 생각한다.

 

좋은 아이디어를 얻으면 구현은 쉽게 할 수 있지만, 좋은 아이디어를 얻기가 쉽지 않았다.

 

다행히 따로 신경 쓸 예외사항은 없었다.