문자열이 하나 주어졌을 때, 문자열을 두 부분으로 나누는 지점 중 왼쪽 부분과 오른쪽 부분이 정확히 같은 문자 집합을 포함하는 위치, 즉 '균형 위치(balance point)'의 개수를 찾는 문제입니다. 이때 각 문자의 등장 빈도는 중요하지 않으며, 해당 문자가 양쪽에 존재하기만 하면 됩니다.
예를 들어 문자열이 "ABAABA"라고 한다면, 균형 위치는 총 3개입니다.
- AB | AABA
- ABA | ABA
- ABAA | BA
해결 접근 방식
이 문제는 효율적인 방식으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 먼저 문자열을 한 번 순회하면서 모든 문자의 개수를
right[]배열에 저장합니다. - 그다음 문자열을 왼쪽에서 오른쪽으로 순회하면서, 현재 문자의 개수를
left[]에서는 1 증가시키고right[]에서는 1 감소시킵니다. - 각 지점에서
left[]에 값이 있는(0이 아닌) 모든 문자가right[]에도 존재하고, 그 반대도 성립하는지 검사합니다. 조건을 만족하면 해당 지점은 균형 위치이므로 결과값을 1 증가시킵니다.
이 방식의 시간 복잡도는 O(n × 256)으로, 문자열 길이 n에 대해 선형적으로 동작하며 추가 공간은 고정 크기 배열 2개뿐이므로 사실상 O(1)입니다.
C++ 구현 예제
#include <iostream>
#include <algorithm>
#define MAX_CHAR 256
using namespace std;
int countBalancePoints(string str) {
int left[MAX_CHAR] = {0};
int right[MAX_CHAR] = {0};
// 모든 문자의 개수를 right[]에 미리 계산
for (int i = 0; i < str.length(); i++)
right[str[i]]++;
int count = 0;
for (int i = 0; i < str.length(); i++) {
// 현재 문자를 왼쪽에는 추가, 오른쪽에서는 제거
left[str[i]]++;
right[str[i]]--;
// left와 right의 문자 집합이 일치하는지 확인
int j;
for (j = 0; j < MAX_CHAR; j++) {
if ((left[j] == 0 && right[j] != 0) || (left[j] != 0 && right[j] == 0))
break;
}
// 모든 문자 집합이 일치하면 균형 위치로 카운트
if (j == MAX_CHAR)
count++;
}
return count;
}
int main() {
char str[] = "ABAABA";
cout << "Number of balance points: " << countBalancePoints(str);
}실행 결과
Number of balance points: 3
동작 원리 정리
문자열 "ABAABA"의 경우를 살펴보겠습니다.
- i = 1 (AB | AABA): 왼쪽에는 {A, B}, 오른쪽에도 {A, B}가 존재 → 균형 위치 ✔
- i = 2 (ABA | ABA): 왼쪽 {A, B}, 오른쪽 {A, B} → 균형 위치 ✔
- i = 3 (ABAA | BA): 왼쪽 {A, B}, 오른쪽 {A, B} → 균형 위치 ✔
나머지 분할 지점에서는 한쪽에만 특정 문자가 존재하게 되어 조건을 만족하지 못하므로, 최종 결과는 3이 됩니다.