C++로 풀어보는 예산 내 동일 부분 문자열 찾기 문제

문제 개요

길이가 같은 두 문자열 s와 t가 주어진다고 가정해 봅시다. 우리는 s를 t로 바꾸고자 합니다. 이때 s의 i번째 문자를 t의 i번째 문자로 변경하는 비용은 |s[i] - t[i]|, 즉 두 문자의 ASCII 값 차이의 절댓값으로 정의됩니다. 추가로 정수 maxCost가 주어지며, 총 비용이 maxCost 이하인 조건 안에서 s의 부분 문자열을 t의 대응되는 부분 문자열과 동일하게 변환할 수 있는 최대 길이를 구해야 합니다.

예를 들어 입력이 s = "abcd", t = "bcdf"이고 maxCost가 3이라면, s의 "abc"를 "bcd"로 변환하는 데 드는 비용이 정확히 3이므로 정답은 3이 됩니다.

접근 방법: 슬라이딩 윈도우

이 문제는 슬라이딩 윈도우(Sliding Window) 기법, 즉 투 포인터 방식을 활용하면 O(n) 시간 복잡도로 효율적으로 해결할 수 있습니다. 윈도우의 총 비용이 maxCost를 초과하면 왼쪽 끝을 줄여나가는 방식입니다.

구체적인 풀이 절차는 다음과 같습니다.

• j := 0, sum := 0, ret := 0으로 초기화합니다.

• i를 0부터 s와 t 길이 중 최솟값까지 반복합니다.

  • sum에 |s[i] - t[i]|를 더합니다.

  • sum이 maxCost보다 커지는 동안 다음을 반복합니다.

    • sum에서 |s[j] - t[j]|를 뺍니다.

    • j를 1 증가시켜 윈도우의 왼쪽 경계를 오른쪽으로 이동합니다.

  • ret을 ret과 (i - j + 1) 중 더 큰 값으로 갱신합니다.

• 반복이 끝나면 ret을 반환합니다.

C++ 구현 예제

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

class Solution {
public:
    int equalSubstring(string s, string t, int maxCost) {
        int j = 0;
        int sum = 0;
        int ret = 0;
        for(int i = 0; i < min((int)s.size(), (int)t.size()); i++){
            sum += abs(s[i] - t[i]);
            while(sum > maxCost){
                sum -= abs(s[j] - t[j]);
                j++;
            }
            ret = max(ret, i - j + 1);
        }
        return ret;
    }
};

입력

"abcd"
"bcdf"
3

출력

3

복잡도 분석

포인터 i와 j는 각각 문자열을 한 번씩만 순회하므로 시간 복잡도는 O(n)입니다. 또한 추가적인 자료구조 없이 몇 개의 변수만 사용하므로 공간 복잡도는 O(1)입니다. 슬라이딩 윈도우 기법 덕분에 모든 부분 문자열 조합을 일일이 검사하는 O(n²) 이상의 비효율적인 방식을 피할 수 있습니다.