여는 괄호 '('와 닫는 괄호 ')'로만 이루어진 문자열 s가 주어졌을 때, 이 문자열이 균형 잡힌(balanced) 상태라고 할 수 있는 조건은 다음과 같습니다.
- 모든 여는 괄호 '('에는 반드시 연속된 두 개의 닫는 괄호 '))'가 대응되어야 합니다.
- 여는 괄호 '('는 반드시 자신과 대응하는 '))'보다 먼저 나와야 합니다.
예를 들어 "())"나 "())(())))"은 균형이 잡힌 문자열이지만, ")()"나 "()))"은 균형이 맞지 않습니다. 이처럼 균형이 깨진 문자열이 주어질 때, 균형을 맞추기 위해 삽입해야 하는 괄호(여는 괄호 또는 닫는 괄호)의 최소 개수를 구하는 것이 문제입니다.
예를 들어 입력이 s = "(())))))"라고 해보겠습니다. 문자열을 잘라 보면 "(())" 뒤에 '))' 덩어리 두 개가 붙어 있는 형태인데, 여는 괄호는 두 개뿐이므로 네 개의 ')'만 소비할 수 있습니다. 따라서 남는 '))' 하나를 짝지어 줄 여는 괄호 한 개를 삽입해야 하고, 정답은 1이 됩니다.
접근 방법
문자열을 왼쪽부터 한 글자씩 훑으면서, 아직 짝을 만나지 못한 여는 괄호의 개수를 변수 o로 관리합니다. 닫는 괄호를 만날 때마다 바로 다음 문자까지 함께 확인해 '))' 쌍을 처리하고, 짝이 맞지 않는 경우 삽입 횟수(ret)를 늘려 주는 방식입니다.
- o := 0(대응되지 않은 여는 괄호 수), n := 문자열 길이로 초기화합니다.
- ret := 0(삽입 횟수), i := 0(현재 인덱스)로 초기화합니다.
- i < n인 동안 다음을 반복합니다.
- s[i]가 '('이면 o를 1 증가시킵니다.
- s[i]가 ')'이면 다음 문자를 확인합니다.
- 다음 문자도 ')'라면 '))' 쌍입니다. o가 0이면 짝이 없으므로 ret를 1 증가시키고, 그렇지 않으면 o를 1 감소시킨 뒤 인덱스를 하나 더 전진시켜 두 문자를 한 번에 처리합니다.
- 다음 문자가 ')'가 아니라면 단독 ')'이므로 ret를 1 증가시킵니다(닫는 괄호 하나 삽입). 이때 o가 0이면 여는 괄호도 부족하므로 ret를 한 번 더 증가시키고, o가 남아 있다면 o를 1 감소시킵니다.
- 반복이 끝나면 ret + 2 × o를 반환합니다. 아직 짝을 찾지 못한 여는 괄호 하나당 '))' 두 개가 더 필요하기 때문입니다.
구현 예제
def solve(s):
o = 0
n = len(s)
ret = 0
i = 0
while i < n:
if s[i] == '(':
o += 1
else:
if i + 1 < n and s[i + 1] == ')':
if not o:
ret += 1
else:
o -= 1
i += 1
else:
ret += 1
if not o:
ret += 1
else:
o -= 1
i += 1
return ret + 2 * o
s = "(())))))"
print(solve(s))입력
"(())))))"
출력
1
코드 동작 살펴보기
예제 입력 "(())))))"에 대해 코드가 어떻게 동작하는지 단계별로 살펴보겠습니다.
- 앞의 두 개의 '('를 만나 o가 2가 됩니다.
- 이후 연속된 '))'를 두 번 만나면서 o가 차례로 감소해 0이 됩니다.
- 마지막 '))'를 만났을 때 o가 0이므로, 짝이 되는 여는 괄호가 없다는 뜻으로 ret가 1 증가합니다.
- 반복이 끝나면 ret + 2 × o = 1 + 0 = 1이 반환됩니다.
복잡도 분석
이 알고리즘은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 몇 개의 정수 변수만 사용하므로 공간 복잡도는 O(1)입니다. 문자열 길이가 매우 길어도 효율적으로 동작합니다.