Sliding Window Algorithm

1. Sliding Window Algorithm이란 ?

윈도우라는 하나의 창(?), 칸을 일정하게 유지하면서 문제에 부합하는 값을 찾아내는 알고리즘이다.

2. Sliding Window Algorhm의 장점

불필요하게 모든 요소들을 중복으로 접근할 필요가 없기 때문에, 시간복잡도를 줄여줄 수 있다.

 

3. 문제를 접근하는 방법

- String, Arrays, LinkedList와 같이 연속적으로 다뤄지는 변수들을 사용할때

- min, max, longer, shortest, contain 등의 문제를 풀어야할때 이 알고리즘을 사용하기에 적합하다.

 

4. 예시와 해결법

• Window Size가 고정인 케이스 :
  • subarray의 길이(k)가 3일때, max(sum)값을 구하여라.

public class MainClass {
	public static int findMaxSumSubarray(int[] arr, int k) {
		int maxValue = Integer.MIN_VALUE;
		int currentRunningSum = 0;
		
		for(int i=0; i<arr.length; i++) {
			currentRunningSum += arr[i];
			if(i >= k-1) {
				maxValue = Math.max(maxValue, currentRunningSum);
				currentRunningSum -= arr[i - (k-1)];
			}
		}
		return maxValue;
	}
	public static void main(String[] args) {
		System.out.println(findMaxSumSubarray(new int[]{4,2,1,7,8,1,2,8,1,0}, 3));
	}

}

• Window Size가 가변인 케이스 :
  • 어떤 값보다 크거나 같은 subarray 중 min(sum) 값을 구하여라

ex:) 8보다 큰 subarray중 가장 작은 size 값을 구하여라(Smallest subarray with given sum 8)

public static int findMaxSumSubarray(int[] arr, int targetSum) {
		int minWindowSize = Integer.MAX_VALUE;
		int currentRunningSum = 0;
		int windowStart = 0;
		for(int windowEnd=0; windowEnd<arr.length; windowEnd++) {
			currentRunningSum += arr[windowEnd];
			while(currentRunningSum >= targetSum) {
				minWindowSize = Math.min(minWindowSize, windowEnd - windowStart + 1);
				currentRunningSum -= arr[windowStart];
				windowStart++;
			}
		}
		return minWindowSize;
	}
	public static void main(String[] args) {
		System.out.println(findMaxSumSubarray(new int[]{4,2,1,7,8,1,2,8,1,0}, 8));
	}

• Window Size가 가변인 케이스(Hashmap과 Hashset등 보조적인 자료구조를 사용) :
  • substring의 가장 큰 값을 구하여라, 단 이 substring은 중복되는 알파벳이 발생하지 않는다.

ex:) Longest Substring Length with K Distinct Characters

public static int findMaxLengthSubarray(String str, int k) {
		int windowStart = 0, maxLength = 0;
	    HashMap<Character, Integer> charFrequencyMap = new HashMap<>();
	    for (int windowEnd = 0; windowEnd < str.length(); windowEnd++) {
	      char rightChar = str.charAt(windowEnd);
	      charFrequencyMap.put(rightChar, charFrequencyMap.getOrDefault(rightChar, 0) + 1);
	
	      while (charFrequencyMap.size() > k) {
	        char leftChar = str.charAt(windowStart);
	        charFrequencyMap.put(leftChar, charFrequencyMap.get(leftChar) - 1);
	        if (charFrequencyMap.get(leftChar) == 0) {
	          charFrequencyMap.remove(leftChar);
	        }
	        windowStart++;
	      }
	      maxLength = Math.max(maxLength, windowEnd - windowStart + 1); 
	    }
	    return maxLength;
	}

이 문제들의 공통점은 ?

-> 모든것들이 연속적으로 그룹핑되어있다.

-> longest, shortest, larget, contained등의 값을 찾는 문제이다.

 

 

 

출처 : https://youtu.be/MK-NZ4hN7rs