Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 풀어보는 '가장 긴 반복 문자 교체' 문제 – 슬라이딩 윈도우 알고리즘 완벽 정리

문제 개요

대문자 알파벳으로만 구성된 문자열 s가 주어지고, 이 문자열에 최대 k번의 연산을 수행할 수 있다고 가정해 봅시다. 한 번의 연산에서는 문자열 내 임의의 문자 하나를 골라 다른 대문자로 변경할 수 있습니다.

이때, 위 연산을 수행한 후 얻을 수 있는 모든 문자가 동일하게 반복되는 가장 긴 부분 문자열(substring)의 길이를 구하는 것이 목표입니다.

예를 들어 입력이 "ABAB"이고 k = 2라면, 출력은 4가 됩니다. 두 개의 'A'를 'B'로 바꾸거나, 두 개의 'B'를 'A'로 바꾸면 전체가 같은 문자로 채워진 길이 4의 부분 문자열을 만들 수 있기 때문입니다.

해결 접근 방식: 슬라이딩 윈도우 + 빈도 카운팅

이 문제는 슬라이딩 윈도우(Sliding Window) 기법과 각 알파벳의 등장 횟수를 추적하는 빈도 배열을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

  • 현재 윈도우 내에서 가장 많이 등장한 문자의 개수(maxCount)를 제외한 나머지 문자들의 개수가 k 이하라면, 그 나머지 문자들을 모두 교체하여 윈도우 전체를 같은 문자로 만들 수 있습니다.
  • 즉, (윈도우 길이) - maxCount > k인 경우에는 윈도우 크기를 줄여야 합니다.

알고리즘 단계

  1. maxCount = 0, ans = 0, n = s.size()로 초기화합니다.
  2. 크기 26의 빈도 배열 cnt와 윈도우 시작 인덱스 j = 0을 선언합니다.
  3. i를 0부터 n-1까지 순회하며 다음을 반복합니다.
    • cnt[s[i] - 'A']를 1 증가시킵니다.
    • maxCount를 현재 문자의 빈도와 비교해 갱신합니다.
    • j <= i이면서 (i - j + 1) - maxCount > k인 동안, 윈도우 왼쪽 끝 문자의 빈도를 감소시키고 j를 증가시켜 윈도우를 축소합니다.
    • ans를 현재 윈도우 길이 (i - j + 1)과 비교해 최댓값으로 갱신합니다.
  4. 최종적으로 ans를 반환합니다.

C++ 구현 예제

아래 코드를 통해 실제 구현 방법을 확인해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int characterReplacement(string s, int k) {
        int maxCount = 0;
        int ans = 0;
        int n = s.size();
        vector<int> cnt(26);
        int j = 0;
        for(int i = 0; i < n; i++){
            cnt[s[i] - 'A']++;
            maxCount = max(maxCount, cnt[s[i] - 'A']);
            while(j <= i && i - j + 1 - maxCount > k){
                --cnt[s[j] - 'A'];
                j++;
            }
            ans = max(ans, i - j + 1);
        }
        return ans;
    }
};
main(){
    Solution ob;
    cout << ob.characterReplacement("ABAB", 2);
}

입력

"ABAB"
2

출력

4

복잡도 분석

  • 시간 복잡도: O(n) — 문자열을 한 번만 순회하며 처리하므로 매우 효율적입니다.
  • 공간 복잡도: O(26) = O(1) — 알파벳 빈도를 저장하는 고정 크기 배열만 사용합니다.

이처럼 슬라이딩 윈도우와 빈도 카운팅을 결합하면, 브루트 포스 방식(O(n²))보다 훨씬 빠르게 문제를 해결할 수 있습니다. 코딩 테스트나 면접에서 자주 등장하는 유형이니 원리를 꼭 익혀두시길 바랍니다.