문자열(string)은 문자들이 순서대로 나열된 배열입니다. 이 문제에서는 여는 괄호 '('와 닫는 괄호 ')'가 섞여 있는 문자열이 주어지며, 짝이 맞지 않는 불필요한 괄호를 제거하여 전체 문자열의 균형을 맞추는 것이 목표입니다.
먼저 예제를 통해 문제를 살펴보겠습니다.
입력 : ")Tutor)ials(p(oin)t(...)" 출력 : "Tutorials(p(oin)t(...))"
위 예제에서 문자열 앞부분의 닫는 괄호 두 개는 짝을 이루는 여는 괄호가 없으므로 제거됩니다. 반면 중간의 여는 괄호 '(p'와 '(oin'에는 대응하는 닫는 괄호가 부족하므로, 문자열 끝에 닫는 괄호를 추가하여 균형을 완성합니다.
알고리즘
이 문제는 별도의 스택 자료구조 없이, 현재 열려 있는 괄호의 개수를 세는 카운터 변수 하나만으로 해결할 수 있습니다. 동작 과정은 다음과 같습니다.
- 1단계 : 문자열을 왼쪽에서 오른쪽으로 한 글자씩 순회합니다.
- 2단계 : 여는 괄호 '('를 만나면 그대로 출력하고 카운트(count)를 1 증가시킵니다.
- 3단계 : 닫는 괄호 ')'를 만나면 카운트가 0보다 클 때만 출력하고 카운트를 1 감소시킵니다. 카운트가 0이라면 짝이 되는 여는 괄호가 없다는 의미이므로 해당 닫는 괄호는 버립니다.
- 4단계 : 괄호가 아닌 일반 문자는 조건 없이 모두 그대로 출력합니다.
- 5단계 : 순회가 끝난 후 카운트가 0이 아니라면, 남은 여는 괄호의 수만큼 닫는 괄호 ')'를 문자열 끝에 추가합니다.
C++ 구현 예제
#include<iostream>
#include<string.h>
using namespace std;
void balancedbrackets(string str){
int count = 0, i;
int n = str.length();
for (i = 0; i < n; i++) {
if (str[i] == '(') {
cout << str[i];
count++;
}
else if (str[i] == ')' && count != 0) {
cout << str[i];
count--;
}
else if (str[i] != ')')
cout << str[i];
}
if (count != 0)
for (i = 0; i < count; i++)
cout << ")";
}
int main() {
string str = ")Tutor)ials(p(oin)t(...)";
cout<<"원본 문자열 : "<<str;
cout<<"\n균형 잡힌 문자열 : ";
balancedbrackets(str);
return 0;
}
실행 결과
원본 문자열 : )Tutor)ials(p(oin)t(...) 균형 잡힌 문자열 : Tutorials(p(oin)t(...))
동작 원리 정리
이 알고리즘의 핵심은 '현재까지 열린 채로 남아 있는 괄호의 개수'를 추적하는 것입니다. 여는 괄호는 언제든 출력해도 안전하지만, 닫는 괄호는 대응되는 여는 괄호가 이미 등장한 경우에만 유효합니다. 따라서 카운트가 0일 때 등장하는 닫는 괄호는 모두 무시하면 됩니다.
반대로 문자열을 모두 훑은 뒤에도 카운트가 남아 있다면, 그만큼의 여는 괄호가 아직 닫히지 않은 상태이므로 필요한 만큼의 닫는 괄호를 뒤에 덧붙여 균형을 완성합니다.
이 방식은 문자열을 한 번만 순회하므로 시간 복잡도가 O(n)이며, 추가 메모리 사용도 상수 수준(O(1))으로 매우 효율적입니다. 스택 기반 접근법보다 구현이 단순하면서도 동일한 결과를 얻을 수 있다는 점이 큰 장점입니다.