C++ 알고리즘: 길이 k인 부분 문자열에서 최대 모음 개수 구하기

문제 소개

문자열 s와 정수 k가 주어졌을 때, 길이가 정확히 k인 모든 부분 문자열(substring) 중에서 모음(vowel) 문자가 가장 많이 포함된 경우의 개수를 구하는 문제입니다.

예를 들어 입력이 s = "abciiidef", k = 3이라면, 길이 3인 부분 문자열 중 "iii"에 모음이 3개로 가장 많으므로 출력은 3이 됩니다.

해결 접근 방법: 슬라이딩 윈도우(Sliding Window)

모든 부분 문자열을 매번 새로 검사하면 비효율적입니다. 대신 슬라이딩 윈도우 기법을 사용하면 한 번의 순회로 답을 구할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

먼저 첫 k개 문자에 포함된 모음 개수를 계산합니다.
이후 윈도우를 오른쪽으로 한 칸씩 이동하면서, 빠져나가는 왼쪽 문자가 모음이면 개수를 1 감소시키고, 새로 들어오는 오른쪽 문자가 모음이면 1 증가시킵니다.
매 이동마다 현재 모음 개수와 기록된 최댓값을 비교하여 갱신합니다.

알고리즘 단계

카운터 cnt := 0으로 초기화하고, 모음을 저장할 집합(set) m을 정의한 뒤 'a', 'e', 'i', 'o', 'u'를 삽입합니다.
결과값 ret := 0으로 초기화합니다.
i = 0부터 k-1까지 반복하며 s[i]가 m에 있으면 cnt를 1씩 증가시켜 첫 윈도우의 모음 수를 셉니다.
ret := max(ret, cnt)로 최댓값을 갱신합니다.
n := s의 길이로 설정합니다.
i = k부터 n-1까지 반복하며 다음을 수행합니다.
- s[i-k]가 m에 속하면 cnt를 1 감소시킵니다(윈도우에서 빠지는 문자).
- s[i]가 m에 속하면 cnt를 1 증가시킵니다(새로 들어오는 문자).
- ret := max(ret, cnt)로 최댓값을 갱신합니다.
반복이 끝나면 ret을 반환합니다.

C++ 구현 예제

아래 코드를 통해 실제 동작을 더 잘 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int maxVowels(string s, int k) {
        int cnt = 0;
        set<char> m;
        for (auto it : { 'a', 'e', 'i', 'o', 'u' })
        m.insert(it);
        int ret = 0;
        for (int i = 0; i < k; i++) {
            cnt += m.count(s[i]) ? 1 : 0;
        }
        ret = max(ret, cnt);
        int n = s.size();
        for (int i = k; i < n; i++) {
            if (m.count(s[i - k])) {
                cnt--;
            }
            cnt += m.count(s[i]) ? 1 : 0;
            ret = max(ret, cnt);
        }
        return ret;
    }
};
main(){
    Solution ob;
    cout << (ob.maxVowels("abciiidef",3));
}

입력

"abciiidef", 3

출력

복잡도 분석

이 알고리즘은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n), 모음 집합 저장에 상수 공간을 사용하므로 공간 복잡도는 O(1)입니다. 브루트포스 방식(O(n×k))보다 훨씬 효율적이며, 특히 문자열이 길거나 k가 큰 경우에 그 차이가 두드러집니다.