문자열 s가 주어졌다고 가정해 봅시다. 이 문자열은 여는 괄호 '('와 닫는 괄호 ')'로만 구성되어 있습니다. 우리가 구해야 할 것은 이 문자열 안에서 가장 긴 유효한(잘 짜여진) 괄호 부분 문자열의 길이입니다.
예를 들어 입력이 ")()(())())" 형태인 ")((())())" 라면, 가장 긴 유효한 부분 문자열은 "(())()"이므로 결과는 6이 됩니다.
문제 해결 접근 방법
이 문제는 스택(Stack)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 문자의 인덱스를 스택에 저장하면서, 유효한 괄호 쌍이 완성될 때마다 현재 위치와 마지막 기준점 사이의 거리를 계산하는 것입니다. 해결 단계는 다음과 같습니다.
스택을 하나 만들고 초기값으로 -1을 넣어 기준점 역할을 하게 합니다. 그리고 정답 변수 ans := 0으로 초기화합니다.
i를 0부터 (문자열 길이 - 1)까지 순회합니다.
s[i]가 여는 괄호 '('라면, 인덱스 i를 스택에 push합니다.
그렇지 않다면(닫는 괄호 ')'라면):
스택이 비어 있지 않고, 스택의 top이 -1이 아니며, s[스택 top]이 여는 괄호라면:
스택에서 top 요소를 pop합니다.
ans := max(ans, i - 스택 top)으로 갱신하여 현재까지의 최대 길이를 유지합니다.
유효한 매칭이 불가능한 경우에는 인덱스 i를 스택에 push하여 새로운 기준점으로 사용합니다.
순회가 끝나면 ans를 반환합니다.
동작 원리 살펴보기
스택에 -1을 먼저 넣는 이유는 '마지막으로 유효하지 않았던 지점'을 표시하기 위함입니다. 닫는 괄호가 여는 괄호와 성공적으로 매칭되면 해당 인덱스들이 스택에서 제거되고, 그 시점의 스택 top은 바로 직전의 기준점이 됩니다. 따라서 현재 인덱스에서 top을 빼면 연속된 유효 괄호 문자열의 길이가 계산됩니다. 매칭에 실패한 닫는 괄호는 새로운 기준점으로 스택에 남게 되어, 이후 길이 계산의 시작점 역할을 하게 됩니다.
예제 코드
다음 구현을 통해 더 잘 이해해 보겠습니다.
class Solution(object):
def solve(self, s):
stack = [-1]
ans = 0
for i in range(len(s)):
if s[i] == "(":
stack.append(i)
else:
if stack and stack[-1] != -1 and s[stack[-1]] == "(":
stack.pop()
ans = max(ans, i - stack[-1])
else:
stack.append(i)
return ans
ob = Solution()
print(ob.solve("))(())())"))입력
"))(())())"
출력
6
복잡도 분석
이 알고리즘은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n), 스택에 인덱스를 저장하므로 공간 복잡도 역시 최악의 경우 O(n)입니다. n은 문자열의 길이입니다.