'(' 와 ')' 두 가지 문자로만 구성된 괄호 시퀀스 s와 t가 주어졌다고 가정해 보겠습니다. 우리가 확인해야 할 것은 이 두 문자열을 이어 붙였을 때 그 결과가 균형 잡힌(balanced) 문자열이 되는지 여부입니다. 연결 순서는 s | t 또는 t | s 두 가지가 가능하며, 어느 한쪽이라도 균형이 맞으면 True를 반환해야 합니다.
예를 들어 입력이 s = "()()))", t = "()(()(" 라면 결과는 True입니다. t | s 순서로 연결하면 "()(()(()()))"라는 문자열이 만들어지는데, 이 문자열은 모든 괄호의 짝이 올바르게 맞아떨어지는 균형 잡힌 문자열이기 때문입니다.
문제 해결 접근 방법
이 문제는 스택(stack) 자료구조를 활용하면 효율적으로 해결할 수 있습니다. 전체적인 흐름은 다음과 같습니다.
- 문자열 하나를 인자로 받는 is_balanced_parenthesis() 함수를 정의합니다.
- 빈 리스트 stack을 생성합니다.
- 문자열의 첫 번째 문자부터 마지막 문자까지 순서대로 순회합니다.
- 현재 문자가 '('라면 스택에 push(추가)합니다.
- 현재 문자가 ')'라면 스택이 비어 있는지 먼저 확인합니다. 비어 있다면 여는 괄호 없이 닫는 괄호가 나온 것이므로 즉시 False를 반환하고, 비어 있지 않다면 스택에서 pop(제거)합니다.
- 순회가 끝난 후에도 스택에 요소가 남아 있다면 짝을 찾지 못한 여는 괄호가 있다는 의미이므로 False를 반환합니다.
- 모든 검사를 통과했다면 True를 반환합니다.
메인 로직에서는 두 가지 연결 순서를 모두 검사합니다. 먼저 is_balanced_parenthesis(s + t)의 결과가 참이면 True를 반환하고, 그렇지 않다면 is_balanced_parenthesis(t + s)의 결과를 최종 답으로 반환합니다.
구현 예제
def is_balanced_parenthesis(string):
stack = []
for i in range(len(string)):
if string[i] == '(':
stack.append(string[i])
else:
if len(stack) == 0:
return False
else:
stack.pop()
if len(stack) > 0:
return False
return True
def solve(s, t):
if is_balanced_parenthesis(s + t):
return True
return is_balanced_parenthesis(t + s)
s = "()()))"
t = "()(()("
print(solve(s, t))입력
"()()))", "()(()("출력
True
동작 원리 살펴보기
이 알고리즘의 핵심은 여는 괄호와 닫는 괄호의 짝을 스택으로 관리하는 것입니다. '('를 만날 때마다 스택에 쌓고, ')'를 만날 때마다 가장 최근에 쌓인 '('를 제거합니다. 처리 과정 중 스택이 비어 있는 상태에서 ')'가 등장하면 잘못된 순서의 괄호가 있다는 뜻이므로 바로 실패를 판정할 수 있습니다. 반대로 끝까지 처리한 후 스택에 '('가 남아 있으면 닫히지 않은 괄호가 존재한다는 의미입니다. 따라서 최종적으로 스택이 완전히 비어 있을 때만 해당 문자열을 균형 잡힌 것으로 판단합니다.
이 방식의 시간 복잡도는 문자열 길이에 비례하여 O(n)이며, 공간 복잡도 역시 최악의 경우 O(n)입니다. 두 문자열의 연결 순서를 각각 한 번씩만 검사하면 되므로 전체 수행 시간도 선형 시간 안에 처리됩니다.