Python으로 가장 긴 균형 괄호 부분 수열의 길이 구하기

문제 설명

여는 괄호 '('와 닫는 괄호 ')'로만 이루어진 문자열 s가 주어졌을 때, 가장 긴 균형 잡힌(balanced) 부분 수열의 길이를 찾아야 합니다.

예를 들어, 입력 문자열이 s = "())(()(" 라면 출력은 4가 됩니다. 왜냐하면 "()()"와 같은 균형 잡힌 부분 수열을 만들 수 있기 때문입니다.

해결 접근 방법

이 문제는 문자열을 오른쪽에서 왼쪽으로 탐색하면서 그리디(greedy) 방식으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• 닫는 괄호 ')'를 먼저 세어둡니다(close 카운터).
• 여는 괄호 '('를 만났을 때, 아직 매칭되지 않은 닫는 괄호가 있다면 한 쌍을 이루었으므로 결과에 2를 더합니다.
• 매칭 가능한 닫는 괄호가 없다면 해당 여는 괄호는 버립니다.

구체적인 알고리즘 단계는 다음과 같습니다.

1. res := 0 (결과 길이 초기화)
2. n := 문자열 s의 길이
3. close := 0 (매칭 대기 중인 닫는 괄호 개수)
4. i를 n-1부터 0까지 1씩 감소시키며 반복:
   • s[i]가 ')'라면 → close를 1 증가
   • 그렇지 않고(즉 '('라면) close > 0이라면 → close를 1 감소하고 res에 2를 더함
5. res를 반환합니다.

시간 복잡도는 O(n), 공간 복잡도는 O(1)로 매우 효율적입니다.

예제 코드

아래는 위 알고리즘을 Python으로 구현한 코드입니다.

class Solution:
    def solve(self, s):
        res = 0
        n = len(s)
        close = 0
        for i in range(n - 1, -1, -1):
            if s[i] == ")":
                close += 1
            else:
                if close > 0:
                    close -= 1
                    res += 2
        return res

ob = Solution()
s = "())(()("
print(ob.solve(s))

입력

"())(()("

출력

4

동작 과정 살펴보기

입력 "())(()("를 오른쪽에서 왼쪽으로 살펴보면 다음과 같습니다.

최종적으로 res = 4가 반환되며, 이는 부분 수열 "()()"의 길이와 일치합니다.