C#, Sliding Window, Two Pointers 구현
슬라이딩 윈도우(Sliding Window)는 고정된 크기의 창(Window)을 옆으로 밀면서 데이터를 처리하는 알고리즘 기법인데 중복 계산을 줄여 시간 복잡도를 $O(N)$으로 최적화하는 데 매우 유용하다.1
또한, 매번 처리되는 중복된 요소를 버리지 않고 재사용함으로써 낭비되는 계산을 하지 않음으로써 효율적으로 처리하는 방법이다.2
문자열 처리에서 Dictionary<char, int>나 int[] 배열을 활용해 투 포인터(Two Pointers) 방식으로 직접 구현하면 IndexOf보다 훨씬 효율적인 $O(N)$ 성능의 함수를 만들 수 있다.
Substring 사용은 메모리 할당(GC 과부하)이 발생하여 윈도우가 움직일 때마다 Substring을 호출하면 성능이 급격히 떨어진다. 이때 Span<T> 또는 ReadOnlySpan<char>를 사용하면 메모리 복사 없이 문자열의 특정 구간을 가리킬 수 있다.
1
ReadOnlySpan<char> window = s.AsSpan().Slice(left, right - left + 1);
사용 예제
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 최소 구간 찾기 (Minimum Window Substring)
// 출력: BANC
const string text1 = "ADOBECODEBANC";
ReadOnlySpan<char> minWin = SlidingWindow.GetMinWindow(text1, "ABC");
LogHelper.Debug($"최소 구간 찾기 : {minWin.ToString()}");
// 중복 없는 가장 긴 문자열 길이
// 출력: 3 (abc)
const string text2 = "abcabcbb";
int longLen = SlidingWindow.GetLongestUniqueLength(text2);
LogHelper.Debug($"중복 없는 최장 길이: {longLen}");
// 애너그램 위치 찾기
// 출력: 0, 6
const string text3 = "cbaebabacd";
List<int> anagrams = SlidingWindow.FindAnagrams(text3, "abc");
LogHelper.Debug($"애너그램 인덱스: {string.Join(", ", anagrams)}");
// K개 고유 문자 포함 최장 길이
// 출력: 3 (ece)
const string text4 = "eceba";
int kLen = SlidingWindow.GetMaxKUniqueLength(text4, 2);
LogHelper.Debug($"최대 2개 고유문자 최장 길이: {kLen}");