균형 잡힌 괄호 '('와 ')'로만 이루어진 문자열 s가 주어졌을 때, 이 문자열을 가장 많은 수의 균형 잡힌 그룹으로 분할하는 것이 목표입니다. 여기서 균형 잡힌 그룹이란, 그룹 내부에서 열림 괄호와 닫힘 괄호의 개수가 서로 일치하고 어떤 위치에서도 닫힘 괄호가 먼저 나오지 않는 완결된 단위를 의미합니다.
예를 들어 입력이 "(()())()(())"라면, 출력은 다음과 같습니다.
['(()())', '()', '(())']
문제 해결 접근 방식
이 문제는 괄호의 균형 상태를 추적하는 카운터 변수 하나만 있으면 선형 시간에 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 임시 문자열
temp, 결과 리스트groups, 그리고 현재까지의 괄호 균형 상태를 저장할count변수를 준비합니다. - 문자열 s의 각 문자 b를 순회하며 아래 작업을 수행합니다.
count가 0(직전 그룹이 완결됨)이고temp에 내용이 있다면,temp를groups에 추가한 뒤 초기화합니다.- 현재 문자 b를
temp에 이어 붙입니다. - b가 '('라면
count를 1 증가시키고, ')'라면 1 감소시킵니다.
- 순회가 끝난 후 마지막으로 남아 있는
temp를groups에 추가하고 반환합니다.
count가 다시 0이 되는 지점이 곧 하나의 균형 그룹이 완성되는 경계이므로, 해당 지점마다 그룹을 잘라내면 전체 문자열을 최대 개수의 균형 그룹으로 나눌 수 있습니다.
구현 예제
다음 코드를 통해 실제 동작을 확인해 보겠습니다.
class Solution:
def solve(self, s):
temp = ''
groups = []
count = 0
for b in s:
if count == 0 and len(temp) > 0:
groups.append(temp)
temp = ''
temp += b
if b == '(':
count += 1
else:
count -= 1
groups.append(temp)
return groups
s = "(()())()(())"
ob = Solution()
print(ob.solve(s))입력
"(()())()(())"
출력
['(()())', '()', '(())']
복잡도 분석
- 시간 복잡도: O(n) — 문자열의 각 문자를 정확히 한 번씩만 순회합니다.
- 공간 복잡도: O(n) — 결과 그룹을 저장하는 리스트와 임시 문자열이 필요합니다.
이처럼 카운터 기반의 단일 패스(single-pass) 접근법을 사용하면 추가적인 스택이나 정규표현식 없이도 간결하고 효율적으로 문제를 해결할 수 있습니다.