프로그래밍 문제에서 자주 등장하는 과제 중 하나는 문자열에 포함된 괄호가 균형 잡혀 있는지 확인하는 것입니다. 이번 글에서는 추가 메모리를 거의 사용하지 않는 O(1) 공간 복잡도와 O(N²) 시간 복잡도로 이 문제를 해결하는 파이썬 방법을 살펴보겠습니다.
문제 정의
여섯 종류의 괄호 문자인 '(', ')', '{', '}', '[', ']'로 구성된 문자열 str이 주어졌을 때, 이 괄호들이 균형 잡혀 있는지 판별해야 합니다. 균형 잡힌 괄호란 다음 조건을 만족하는 경우를 말합니다.
- 여는 괄호와 닫는 괄호의 종류가 서로 일치해야 합니다.
- 괄호가 올바른 순서로 닫혀야 합니다.
예를 들어 입력이 "{([])}"라면 모든 괄호가 올바르게 짝지어져 있으므로 출력은 True입니다.
해결 접근 방식
이 알고리즘은 스택 자료구조를 별도로 생성하지 않고, 원본 문자열 위에서 포인터 두 개(i, j)와 카운터(cnt)만 활용합니다. 핵심 아이디어는 다음과 같습니다.
- cnt := 0, i := 0, j := -1로 초기화합니다.
- solve(s, temp) 함수를 정의합니다. 이 함수는 cnt를 1 감소시키고, 문자열 s를 리스트로 변환한 뒤 아래 로직을 수행합니다.
- j > -1이고 s[j]가 temp와 같다면:
- s[i]와 s[j]를 '#'으로 표시하여 이미 처리된 괄호임을 나타냅니다.
- j가 0 이상이면서 s[j]가 '#'인 동안 j를 계속 감소시켜, 다음 매칭 후보 위치로 되돌아갑니다.
- i를 1 증가시키고 1을 반환합니다(매칭 성공).
- 그렇지 않으면 0을 반환합니다(매칭 실패).
메인 로직의 흐름
- 문자열 길이가 0이면 True를 반환합니다.
- 그렇지 않으면 ans = False로 초기화하고, i가 문자열 길이보다 작은 동안 반복합니다.
- s[i]가 '}'이면 solve(s, '{')를 호출하고, 결과가 0이면 False를 반환합니다.
- s[i]가 ')'이면 solve(s, '(')를 호출하고, 결과가 0이면 False를 반환합니다.
- s[i]가 ']'이면 solve(s, '[')를 호출하고, 결과가 0이면 False를 반환합니다.
- 그 외의 경우(여는 괄호)에는 j := i로 갱신하고, i를 증가시킨 뒤 cnt를 1 증가시킵니다.
- 반복이 끝난 후 cnt가 0이 아니라면 짝이 맞지 않는 여는 괄호가 남아 있다는 뜻이므로 False를 반환합니다.
- 모든 검사를 통과하면 True를 반환합니다.
구현 예제
아래 코드를 통해 실제 동작을 더 잘 이해할 수 있습니다.
cnt = 0
i = 0
j = -1
def solve(s, temp):
global i, j, cnt
cnt -= 1
s = list(s)
if j > -1 and s[j] == temp:
s[i] = '#'
s[j] = '#'
while j >= 0 and s[j] == '#':
j -= 1
i += 1
return 1
else:
return 0
def bracketOrderCheck(s):
global i, j, cnt
if len(s) == 0:
return True
else:
ans = False
while i < len(s):
if s[i] == '}':
ans = solve(s, '{')
if ans == 0:
return False
elif s[i] == ')':
ans = solve(s, '(')
if ans == 0:
return False
elif s[i] == ']':
ans = solve(s, '[')
if ans == 0:
return False
else:
j = i
i += 1
cnt += 1
if cnt != 0:
return False
return True
print(bracketOrderCheck("{([])}"))입력
"{(()[])}"출력
True
마무리
이 방법은 스택을 따로 두지 않고 기존 문자열 내부에서 '#' 마커로 처리된 위치를 덮어쓰기 때문에 추가 공간이 O(1)입니다. 대신 닫는 괄호마다 이전 위치를 되짚어가며 매칭하기 때문에 최악의 경우 O(N²)의 시간이 소요됩니다. 메모리 제약이 엄격한 환경에서 유용하게 활용할 수 있는 기법이니, 일반적인 스택 기반 풀이와 비교하며 학습해 보시길 권장합니다.