문제 정의
하나의 표현식(exp)이 주어졌을 때, 이 표현식에 중복된 괄호 쌍이 존재하는지 확인해야 하는 문제를 생각해 보겠습니다. 어떤 하위 표현식이 두 개 이상의 괄호 쌍으로 둘러싸여 있다면, 그 표현식에는 중복 괄호(duplicate parentheses)가 있다고 합니다.
예를 들어 다음과 같은 표현식이 있다고 가정해 보겠습니다.
(5+((7−3)))
여기서 하위 표현식 (7 − 3)은 두 쌍의 괄호로 둘러싸여 있으므로, 이 표현식에는 중복 괄호가 존재합니다.
스택(Stack)을 활용한 해결 접근
이 문제는 스택 자료구조를 활용하면 효율적으로 해결할 수 있습니다. 알고리즘의 동작 과정은 다음과 같습니다.
- 표현식의 각 문자를 왼쪽부터 순서대로 순회합니다.
- 현재 문자가 열린 괄호 '(' 이거나 연산자, 피연산자라면 스택에 push합니다.
- 현재 문자가 닫힌 괄호 ')' 라면, 짝이 되는 열린 괄호 '(' 를 만날 때까지 스택에서 문자를 반복적으로 pop합니다.
- 이 과정에서 카운터를 사용하여 열린 괄호와 닫힌 괄호 사이에 있던 문자의 개수를 셉니다.
- 카운터 값이 1보다 작다면, 즉 괄호 쌍 사이에 아무런 문자도 없었다면 중복 괄호가 발견된 것이고, 그렇지 않으면 계속 진행합니다.
C++ 구현 예제
#include<iostream>
#include<stack>
using namespace std;
bool hasDuplicateParentheses(string str) {
stack<char> stk;
for (int i = 0; i<str.length(); i++) {
char ch = str[i];
if (ch == ')') {
char top = stk.top();
stk.pop();
int count = 0;
while (top != '(') {
count++;
top = stk.top();
stk.pop();
}
if(count < 1) {
return true;
}
}
else
stk.push(ch);
}
return false;
}
int main() {
string str = "(5+((7-3)))";
if (hasDuplicateParentheses(str))
cout << "Duplicate parentheses has Found";
else
cout << "No Duplicates parentheses has Found ";
}실행 결과
Duplicate parentheses has Found
예제 코드에서 사용한 표현식 (5+((7-3)))에는 중복 괄호가 포함되어 있으므로, 프로그램은 중복 괄호가 발견되었음을 출력합니다.
정리
이 알고리즘은 표현식의 길이를 n이라 할 때 각 문자를 한 번씩만 처리하므로 시간 복잡도는 O(n), 공간 복잡도 역시 최악의 경우 모든 문자를 스택에 저장해야 하므로 O(n)입니다. 컴파일러나 수식 파서에서 불필요한 괄호를 검출해야 하는 상황 등에 유용하게 활용할 수 있습니다.