균형 문자열 분할 문제란?
균형 문자열(balanced string)이란 'L'과 'R' 두 문자의 개수가 서로 동일한 문자열을 의미합니다. 이번 문제에서는 균형 상태를 이룬 문자열 s가 주어졌을 때, 이를 가능한 한 많은 균형 문자열 조각으로 분리하고, 그 최대 분할 개수를 반환해야 합니다.
예를 들어 입력 문자열이 "RLRRLLRLRL"이라면 결과값은 4입니다. 이 문자열은 "RL", "RRLL", "RL", "RL"이라는 네 개의 부분 문자열로 나눌 수 있으며, 각 부분 문자열 모두 'L'과 'R'의 개수가 정확히 일치하기 때문입니다.
해결 접근 방식
이 문제는 카운터 하나만 활용하면 손쉽게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 카운터 cnt와 정답 변수 ans를 0으로 초기화합니다.
- 문자열을 앞에서부터 순회하며, 'R'을 만나면 cnt를 1 증가시키고, 'L'을 만나면 1 감소시킵니다.
- 순회 중 cnt가 0이 되는 지점이 곧 하나의 균형 구간이 끝나는 위치입니다. 이때 ans를 1 증가시키고, 해당 위치부터 새로운 탐색을 시작합니다.
- 모든 문자를 확인한 후 ans를 반환합니다.
cnt가 0이 된다는 것은 지금까지 살펴본 구간 안에 'R'과 'L'의 개수가 정확히 같다는 뜻이므로, 그 즉시 잘라내는 것이 항상 최적의 선택이 됩니다(그리디 전략).
C++ 구현 예제
아래 코드를 통해 보다 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int balancedStringSplit(string s) {
int cnt = 0;
int ans = 0;
for(int i =0;i<s.size();i++){
cnt = 0;
for(int j = i;j<s.size();j++){
if(s[j] == 'R')cnt++;
else cnt--;
if(j-i>0 && cnt == 0 ){
ans++;
i=j;
break;
}
}
}
return ans;
}
};
main(){
Solution ob;
cout << ob.balancedStringSplit("RLLLLRRRLR");
}
입력
"RLLLLRRRLR"
출력
3
동작 과정 분석
입력 "RLLLLRRRLR"에 대해 위 코드는 다음과 같이 세 번 분할을 수행합니다.
- "RL" : 첫 두 문자에서 cnt가 0이 되어 첫 번째 균형 구간이 완성됩니다.
- "LLLLRRR" : 'L' 세 개로 음수가 된 카운터가 이후 'R' 세 개로 다시 0이 됩니다.
- "LR" : 마지막 남은 두 문자로 세 번째 균형 구간이 완성됩니다.
따라서 최종 결과는 3이 반환됩니다.
복잡도 및 개선 팁
위 구현은 최악의 경우 O(n²) 시간 복잡도를 가질 수 있습니다. 하지만 사실 외부 반복문 없이 문자열을 한 번만 순회해도 충분합니다. 즉, 단일 패스(single pass)로 카운터를 갱신하다가 cnt가 0이 될 때마다 바로 ans를 증가시키면 O(n) 시간에 문제를 해결할 수 있습니다. 균형 문자열이 입력으로 보장되어 있으므로, 매 순간 잘라내는 그리디 선택이 항상 최대 분할 개수를 보장합니다.