괄호로만 이루어진 문자열이 주어졌을 때, 모든 여는 괄호가 반드시 닫히는 '올바른' 문자열을 만들기 위해 제거해야 할 괄호의 최소 개수를 구하는 문제입니다.
예를 들어 입력이 "(()))(" 라면, 올바른 문자열은 "(())" 이고 ")(" 부분을 제거하면 되므로 정답은 2가 됩니다.
문제 해결 접근 방식
이 문제는 스택 없이도 두 개의 카운터 변수만으로 효율적으로 해결할 수 있습니다.
total: 아직 짝이 맞지 않는 여는 괄호 '(' 의 개수temp: 매칭에 실패한 닫는 괄호 ')' 의 개수
알고리즘 단계
total = 0,temp = 0으로 초기화합니다.- 문자열의 각 문자
p에 대해 다음을 검사합니다.p가 '(' 라면 →total을 1 증가시킵니다.p가 ')' 이고total이 0이 아니라면 → 대응되는 여는 괄호가 있으므로total을 1 감소시킵니다.- 그 외의 경우(닫는 괄호인데 짝이 없는 경우) →
temp를 1 증가시킵니다.
- 최종적으로
total + temp를 반환합니다. 각각 짝이 맞지 않는 여는 괄호와 닫는 괄호의 수를 더한 값이 곧 제거해야 할 최소 괄호 수입니다.
파이썬 구현 예제
class Solution:
def solve(self, s):
total = 0
temp = 0
for p in s:
if p == "(":
total += 1
elif p == ")" and total:
total -= 1
else:
temp += 1
return total + temp
ob1 = Solution()
string = "(()))("
print(ob1.solve(string))
실행 결과
입력:
"(()))("출력:
2
동작 원리 살펴보기
입력 "(()))(" 를 순서대로 처리해 보면 다음과 같습니다.
- '(' → total = 1
- '(' → total = 2
- ')' → total = 1 (짝이 맞음)
- ')' → total = 0 (짝이 맞음)
- ')' → total이 0이므로 temp = 1 (제거 대상)
- '(' → total = 1 (끝까지 닫히지 않음, 제거 대상)
최종 결과는 total(1) + temp(1) = 2로, 실제로 제거해야 할 괄호의 최소 개수와 일치합니다.
복잡도 분석
- 시간 복잡도: O(n) — 문자열을 한 번만 순회합니다.
- 공간 복잡도: O(1) — 추가 자료구조 없이 상수 공간만 사용합니다.
스택을 사용하는 일반적인 풀이와 달리, 이 방법은 카운터 두 개만으로 동일한 결과를 얻을 수 있어 메모리 측면에서 더욱 효율적입니다.