문제 설명
'Q', 'W', 'E', 'R' 네 종류의 문자로만 이루어진 문자열이 있다고 가정해 봅시다. 문자열의 길이를 n이라 할 때, 각 문자가 정확히 n/4번씩 등장하면 이 문자열을 균형 잡힌(balanced) 문자열이라고 합니다. 우리가 구해야 하는 값은, 원본 문자열을 균형 잡힌 상태로 만들기 위해 동일한 길이의 다른 문자열로 교체할 수 있는 부분 문자열의 최소 길이입니다.
예를 들어 s = "QQWE"라면 답은 1입니다. Q 하나를 R로 바꾸면 "RQWE"가 되어 균형이 맞기 때문입니다. 이미 균형이 잡혀 있는 문자열이라면 0을 반환합니다.
접근 방법: 슬라이딩 윈도우
이 문제는 슬라이딩 윈도우(Sliding Window) 기법으로 O(n) 시간에 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
어떤 부분 문자열(윈도우)을 교체했을 때 전체가 균형 잡히려면, 윈도우 바깥에 남아 있는 각 문자의 개수가 모두 n/4 이하여야 합니다. 따라서 이 조건을 만족하는 가장 짧은 윈도우를 찾으면 그것이 곧 정답이 됩니다.
알고리즘 단계는 다음과 같습니다.
- 문자 빈도를 저장할 해시맵 m을 생성합니다.
- 문자열 s의 각 문자 빈도를 m에 기록하고, n := s의 길이로 설정합니다.
- res := n, left := 0으로 초기화합니다.
- right를 0부터 n-1까지 순회합니다.
- m[s[right]]를 1 감소시킵니다. (현재 문자를 윈도우 안으로 포함)
- left < n이고 m['Q'] ≤ n/4, m['W'] ≤ n/4, m['E'] ≤ n/4, m['R'] ≤ n/4 조건을 모두 만족하는 동안:
- res := min(res, right − left + 1)
- m[s[left]]를 1 증가시키고 left를 1 늘립니다. (왼쪽 끝 문자를 윈도우 밖으로 제외)
- res를 반환합니다.
C++ 구현 코드
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int balancedString(string s) {
unordered_map<char, int> m;
for(int i = 0; i < s.size(); i++) m[s[i]]++;
int n = s.size();
int res = n;
int left = 0;
for(int right = 0; right < n; right++){
m[s[right]]--;
while(left < n && m['Q'] <= n/4 && m['W'] <= n/4 && m['E'] <= n/4 && m['R'] <= n/4){
res = min(res, right - left + 1);
m[s[left]] += 1;
left++;
}
}
return res;
}
};
main(){
Solution ob;
cout << (ob.balancedString("QQEQ"));
}
실행 결과
입력
"QQEQ"
출력
2
결과 설명: "QQEQ"에는 Q가 3개, E가 1개 있으며 W와 R은 없습니다. 길이 1짜리 부분 문자열을 교체해서는 균형을 맞출 수 없지만, 앞의 두 글자 "QQ"를 "WR"로 바꾸면 "WREQ"가 되어 모든 문자가 정확히 한 번씩 등장하는 균형 잡힌 문자열이 됩니다. 따라서 최소 교체 길이는 2입니다.