문제 개요
문자열이 오직 '('와 ')' 문자로만 구성되고 다음 조건 중 하나를 만족할 때, 이를 유효한 괄호 문자열(Valid Parentheses String, VPS)이라고 합니다.
- 빈 문자열인 경우
- A와 B가 각각 VPS일 때, AB 형태로 표현되는 경우
- A가 VPS일 때, (A) 형태로 표현되는 경우
또한 모든 VPS S에 대해 중첩 깊이 depth(S)를 아래와 같이 정의할 수 있습니다.
- depth("") = 0
- depth(A + B) = max(depth(A), depth(B)), 단 A와 B는 각각 VPS
- depth("(" + A + ")") = 1 + depth(A), 단 A는 VPS
문제 정의
VPS인 문자열 seq가 주어지면, 이를 서로 겹치지 않는 두 부분 수열 A와 B로 분할해야 합니다. 이때 A와 B 역시 각각 VPS여야 하며, 두 수열 길이의 합은 seq의 길이와 같아야 합니다(len(A) + len(B) = len(seq)). 목표는 max(depth(A), depth(B))가 최소가 되도록 A와 B를 선택하는 것입니다. 그리고 그 선택 결과를 seq와 같은 길이의 배열로 인코딩해 반환해야 하는데, answer[i] = 0이면 seq[i]가 A에 속하고, 그렇지 않으면 answer[i] = 1입니다.
예를 들어 입력이 "()(())()"라면 출력은 [1, 1, 1, 0, 1, 0, 1, 1]이 됩니다.
접근 방법: 그리디 균형 배분
이 문제는 그리디(Greedy) 기법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 괄호를 만날 때마다 두 개의 카운터 c1과 c2 중 더 낮은 쪽에 배분하여, 두 그룹의 깊이 차이가 벌어지지 않도록 항상 균형을 유지하는 것입니다.
- n := seq의 길이, res := 길이가 n이고 0으로 초기화된 배열
- c1, c2 := 0, 0 (두 그룹의 현재 깊이를 추적)
- i를 0부터 n-1까지 순회하며 다음을 수행합니다.
- seq[i]가 '('인 경우: c1 < c2이면 c1을 1 증가시키고, 그렇지 않으면 c2를 1 증가시킨 뒤 res[i] := 1로 설정
- seq[i]가 ')'인 경우: c1 > c2이면 c1을 1 감소시키고, 그렇지 않으면 c2를 1 감소시킨 뒤 res[i] := 1로 설정
- 순회가 끝나면 res를 반환합니다.
이처럼 여는 괄호와 닫는 괄호를 두 그룹에 고르게 나누면 어느 한쪽의 깊이가 과도하게 깊어지는 것을 막을 수 있으며, 결과적으로 max(depth(A), depth(B))가 가능한 최솟값에 가장 가깝게 유지됩니다.
Python 구현 예제
class Solution(object):
def maxDepthAfterSplit(self, seq):
n = len(seq)
res = [0] * n
c1, c2 = 0, 0
for i in range(n):
if seq[i] == '(':
if c1 < c2:
c1 += 1
else:
c2 += 1
res[i] = 1
else:
if c1 > c2:
c1 -= 1
else:
c2 -= 1
res[i] = 1
return res
ob = Solution()
print(ob.maxDepthAfterSplit("()(())()"))
입력
"()(())()"
출력
[1, 1, 1, 0, 1, 0, 1, 1]
복잡도 분석
문자열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 결과 배열을 저장하기 위한 공간 복잡도 역시 O(n)입니다.