괄호 문자열의 등점(Equal Point)이란?
이번 글에서는 C++를 활용해 괄호 문자열에서 등점(equal point)을 찾는 방법을 알아보겠습니다. 등점이란 특정 인덱스 i를 기준으로, 그 앞쪽에 있는 여는 괄호 '('의 개수와 그 뒤쪽에 있는 닫는 괄호 ')'의 개수가 정확히 일치하는 지점을 의미합니다.
예를 들어 괄호 문자열이 "(()))(()()())))"라고 가정해 보겠습니다. 각 인덱스별 문자를 자세히 살펴보면 다음과 같습니다.
인덱스 : 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
문자 : ( ( ) ) ) ( ( ) ( ) ( ) ) ) )
인덱스 0부터 9 사이에는 여는 괄호가 총 5개 있고, 인덱스 9부터 14 사이에는 닫는 괄호 역시 총 5개입니다. 따라서 인덱스 9가 바로 이 문자열의 등점입니다.
해결 접근 방법
이 문제는 누적 합(prefix sum) 개념을 활용하면 효율적으로 해결할 수 있습니다. 전체 과정은 다음 세 단계로 요약할 수 있습니다.
- 여는 괄호 누적 개수 계산: 문자열을 왼쪽에서 오른쪽으로 순회하며 각 인덱스 i까지 등장한 여는 괄호의 개수를 배열에 저장합니다.
- 닫는 괄호 누적 개수 계산: 문자열을 마지막 인덱스부터 역방향으로 순회하며 각 인덱스 이후에 등장하는 닫는 괄호의 개수를 배열에 저장합니다.
- 등점 판별: 두 배열을 비교하여 여는 괄호와 닫는 괄호의 개수가 동일한 인덱스를 찾아냅니다.
C++ 구현 예제
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int findEqualPoint(string str) {
int total_length = str.length();
vector<int> open(total_length + 1, 0); // 여는 괄호 누적 개수
vector<int> close(total_length + 1, 0); // 닫는 괄호 누적 개수
int index = -1;
// 첫 문자가 여는 괄호면 open[1]을 1로 설정
if (str[0] == '(')
open[1] = 1;
// 마지막 문자가 닫는 괄호면 close[total_length-1]을 1로 설정
if (str[total_length - 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;
// 닫는 괄호가 하나도 없으면 인덱스 0이 등점
if (close[0] == 0)
return 0;
// open[i] == close[i]가 성립하는 인덱스 탐색
for (int i = 0; i <= total_length; i++)
if (open[i] == close[i])
index = i;
return index;
}
int main() {
string str = "(()))(()()())))";
cout << "등점의 인덱스: " << findEqualPoint(str) << endl;
return 0;
}실행 결과
등점의 인덱스: 9
동작 원리 및 복잡도 분석
위 코드는 먼저 왼쪽에서 오른쪽으로 한 번, 오른쪽에서 왼쪽으로 한 번씩 문자열을 순회하여 두 개의 누적 배열을 만든 뒤, 마지막으로 두 배열의 값을 비교하여 조건을 만족하는 인덱스를 반환합니다.
- 시간 복잡도: O(n) — 문자열을 최대 세 번 선형 순회합니다.
- 공간 복잡도: O(n) — 여는 괄호와 닫는 괄호의 누적 개수를 저장하기 위한 두 개의 보조 배열이 필요합니다.
또한 경계 조건도 처리하고 있습니다. 문자열에 여는 괄호가 전혀 없다면 문자열의 끝(total_length)이 곧 등점이 되고, 반대로 닫는 괄호가 전혀 없다면 인덱스 0이 등점이 됩니다. 만약 조건을 만족하는 지점이 존재하지 않으면 -1을 반환합니다.