문제 이해
문자열 S가 주어졌다고 가정해 봅시다. S에는 두 가지 종류의 문자, 즉 'x'와 'a'만 포함되어 있습니다. 우리가 해야 할 일은 S에서 몇 개의 문자를 제거하여 남은 문자열이 '좋은 문자열(good string)'이 되도록 만들 때, 남길 수 있는 최대 길이를 구하는 것입니다.
여기서 좋은 문자열이란, 문자열 전체 길이의 절반보다 엄격하게 많은 부분이 문자 'a'로 채워진 문자열을 의미합니다.
예시
입력이 S = "xaxxxxa"라고 해봅시다. 이 경우 출력은 3이 됩니다. 'x' 네 개를 제거하면 문자열은 "xaa"가 되는데, 길이 3 중 'a'가 2개로 절반(1.5)보다 많으므로 좋은 문자열 조건을 만족합니다.
접근 방법
이 문제는 간단한 수학적 관찰만으로 해결할 수 있습니다.
- 문자열 S에 포함된 'a'의 개수를 k라고 합시다.
- 좋은 문자열의 길이를 L이라 하면, 조건은 k > L / 2, 즉 L < 2 × k입니다.
- 따라서 좋은 문자열이 가질 수 있는 최대 길이는 2 × k − 1입니다.
- 물론 원래 문자열 길이 n보다 길어질 수는 없으므로, 최종 답은 n과 2 × k − 1 중 더 작은 값입니다.
k := S에 포함된 'a'의 개수
n := 문자열 S의 길이
return min(n, 2 * k - 1)
C++ 구현 예제
아래 구현을 통해 더 잘 이해해 봅시다.
#include <bits/stdc++.h>
using namespace std;
int solve(string S) {
int x = 2 * count(S.begin(), S.end(), 'a') - 1;
int n = S.size();
return min(n, x);
}
int main() {
string S = "xaxxxxa";
cout << solve(S) << endl;
}
입력
"xaxxxxa"
출력
3
코드 설명
count(S.begin(), S.end(), 'a') 함수는 STL 알고리즘으로, 문자열 S 전체에서 'a'가 등장하는 횟수를 세어 반환합니다. 여기에 2를 곱한 뒤 1을 빼면, 'a'가 절반을 초과하도록 유지할 수 있는 최대 문자열 길이가 됩니다. 마지막으로 이 값과 원래 문자열의 길이 n을 비교하여 더 작은 값을 반환하면, 제거 후 남길 수 있는 최대 길이를 얻을 수 있습니다.
이 알고리즘은 문자열을 한 번만 순회하면 되므로 시간 복잡도는 O(n)이며, 추가 메모리 사용 없이 효율적으로 동작합니다.