문제 개요
'(' 와 ')' 두 종류의 괄호로만 이루어진 문자열 S가 주어졌을 때, 임의의 위치에 최소 개수의 괄호를 추가하여 전체 문자열이 유효한(valid) 괄호 문자열이 되도록 만드는 문제입니다.
유효한 괄호 문자열은 다음 조건 중 하나를 반드시 만족해야 합니다.
- 빈 문자열("")인 경우
- XY 형태로 표현할 수 있는 경우 (X와 Y가 각각 유효한 문자열이며 서로 연결된 형태)
- (A) 형태로 표현할 수 있는 경우 (A가 유효한 문자열)
예를 들어 입력 문자열이 "()))((" 라면, 짝이 맞지 않는 닫는 괄호 2개와 여는 괄호 2개가 존재하므로 총 4개의 괄호를 추가해야 유효한 문자열이 됩니다.
접근 방법: 스택(Stack) 활용
이 문제는 스택 자료구조를 사용하면 직관적이고 효율적으로 해결할 수 있습니다. 여는 괄호와 닫는 괄호가 만나면 서로 짝을 이루어 제거하고, 마지막까지 남은 괄호의 개수가 곧 추가해야 할 최소 괄호 수가 됩니다.
풀이 절차는 다음과 같습니다.
- S가 빈 문자열이라면 0을 반환합니다.
- 스택 역할을 할 temp 배열을 준비합니다.
- 문자열 S를 한 글자씩 순회합니다.
- 여는 괄호 '('라면 temp에 삽입(push)합니다.
- 닫는 괄호 ')'라면, temp가 비어 있지 않고 마지막 요소가 '('일 때 마지막 요소를 삭제(pop)합니다. 즉, 짝이 맞는 괄호끼리 제거하는 것입니다. 그렇지 않다면 temp에 삽입합니다.
- 순회가 끝난 후 temp에 남아 있는 요소의 개수를 반환합니다. 남은 요소는 짝을 찾지 못한 괄호들이므로, 이 개수만큼 새로운 괄호를 추가해야 합니다.
예제 코드
class Solution:
def minAddToMakeValid(self, S):
if not S:
return 0
count = 0
temp = []
temp_counter = 0
for i in S:
if i =='(':
temp.append(i)
else:
if len(temp)>0 and temp[len(temp)-1] =='(':
temp.pop(len(temp)-1)
else:
temp.append(i)
return len(temp)
ob = Solution()
print(ob.minAddToMakeValid("()))(("))입력
"()))(("출력
4
동작 원리 및 복잡도 분석
위 코드에서 "()))((" 를 처리하는 과정을 살펴보면 다음과 같습니다.
- 앞의 '(' 는 바로 뒤의 ')' 와 짝을 이루어 스택에서 제거됩니다.
- 그다음 두 개의 ')' 는 짝이 될 여는 괄호가 없으므로 스택에 그대로 남습니다.
- 마지막 두 개의 '(' 는 짝이 될 닫는 괄호가 없으므로 스택에 남습니다.
결국 스택에는 4개의 괄호가 남게 되며, 이것이 곧 추가해야 할 최소 괄호 개수입니다.
시간 복잡도는 문자열을 한 번만 순회하므로 O(n), 공간 복잡도는 최악의 경우 모든 문자가 스택에 저장될 수 있으므로 O(n)입니다.