여기서 우리는 대괄호 문자열에서 동일한 점을 얻는 방법을 볼 것입니다. 등점은 인덱스 I로 앞의 여는 괄호의 수가 뒤의 닫는 괄호의 수와 같도록 합니다. 대괄호 문자열이 "(()))(()()()))"와 같다고 가정하고 자세히 보면
따라서 0에서 9까지의 여는 괄호의 개수는 5이고, 9에서 14까지의 닫는 괄호의 개수도 5이므로 이것이 등점입니다.
이 문제를 해결하려면 다음 몇 단계를 따라야 합니다 -
- 모든 인덱스 i까지 문자열에 나타나는 여는 괄호의 수를 저장합니다.
- 문자열에 나타나는 닫는 괄호의 수를 각 인덱스 I까지 저장하지만 마지막 인덱스부터 수행해야 합니다.
- 인덱스가 여는 괄호와 닫는 괄호 값이 같은지 확인합니다.
예
#include<iostream> #include<cmath> using namespace std; int findEqualPoint(string str) { int total_length = str.length(); int open[total_length+1] = {0}, close[total_length+1] = {0}; int index = -1; open[0] = 0; close[total_length] = 0; if (str[0]=='(') //check whether first bracket is opening or not, if so mark open[1] = 1 open[1] = 1; if (str[total_length-1] == ')') //check whether first bracket is closing or not, if so mark close[end] = 1 close[total_length-1] = 1; for (int i = 1; i < total_length; i++) { if ( str[i] == '(' ) open[i+1] = open[i] + 1; else open[i+1] = open[i]; } for (int i = total_length-2; i >= 0; i--) { if ( str[i] == ')' ) close[i] = close[i+1] + 1; else close[i] = close[i+1]; } if (open[total_length] == 0) return total_length; if (close[0] == 0) return 0; for (int i=0; i<=total_length; i++) if (open[i] == close[i]) index = i; return index; } int main() { string str = "(()))(()()())))"; cout << "Index of equal point: " << findEqualPoint(str); }
출력
Index of equal point: 9