문제 개요
여는 괄호 "("와 닫는 괄호 ")"로만 이루어진 문자열 s가 주어졌다고 가정해 보겠습니다. 이때 문자열 안의 괄호들이 서로 균형을 이루고 있는지 확인해야 합니다.
예를 들어 입력이 s = "(()())(())"라면 모든 괄호가 올바른 순서로 짝을 이루고 있으므로 출력은 True입니다. 반대로 닫는 괄호가 먼저 등장하거나, 여는 괄호가 닫히지 않은 채 문자열이 끝난다면 False를 반환해야 합니다.
풀이 접근 방식
이 문제는 별도의 스택 자료구조 없이 하나의 정수 카운터만으로 간단하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 카운터 num_open을 0으로 초기화합니다.
- 문자열 s의 각 문자 c를 순회하면서 다음을 수행합니다.
- c가 '('라면 num_open을 1 증가시킵니다.
- c가 ')'라면 현재 num_open 값을 확인합니다. 값이 0보다 크면 1 감소시키고, 0이라면 짝이 없는 닫는 괄호이므로 즉시 False를 반환합니다.
- 모든 문자를 검사한 뒤 num_open이 0이면 True, 그렇지 않으면 False를 반환합니다. num_open이 0보다 크다는 것은 닫히지 않은 여는 괄호가 남아 있다는 의미이기 때문입니다.
이 방식은 시간 복잡도 O(n), 공간 복잡도 O(1)로 매우 효율적입니다. 아래 예제를 통해 자세히 살펴보겠습니다.
예제
class Solution:
def solve(self, s):
num_open = 0
for c in s:
if c == '(':
num_open += 1
elif c == ')':
if num_open == 0:
return False
num_open -= 1
return num_open == 0
ob = Solution()
print(ob.solve("(()())(())"))
입력
"(()())(())"
출력
True