Sliding Window (슬라이딩 윈도우) TC O(N) Technique

Sliding Window

Sliding Window란, 배열의 첫번째 인덱스부터 차례대로 접근하되, 해당 인덱스에서 다시 일정 범위 내 원소들에 접근하는 방법이다. 원소의 개수가 N개, Window 크기가 K 개라면, 총 N x K 번의 인덱스 접근이 발생한다. K가 매우 클 때 이러한 방법은 Brute Force와 같아지고 Time Complexity : O(n^2)이 된다.

 

코딩 문제에서 Window 크기 K가 고정되어 있다면 난이도가 낮은 문제로 Sliding Window 개념만 구현해주면 된다.  만약, Window 크기도 변수로 설정된 문제라면 난이도가 중간인 문제이고, 이때는 Time Complexity가 O(n^2)이 아닌 O(n)으로 문제를 풀 수 있는 알고리즘을 생각해야 한다.

 

 Time Complexity O(n^2)의 알고리즘은 n이 커짐에 따라 연산 관점에서 매우 비효율적이다. 보통의 코딩 문제들에선 TC (* Time Complexity) O(n^2)의 답안들은 Time Limit Exceed가 걸리게 된다. 따라서 O(n logn) 혹은 O(n)의 알고리즘을 생각해야 하는데, Sliding Window 개념을 사용하는 코딩 문제도 마찬가지다.

 

 Sliding Window는 TC O(n^2)의 알고리즘을 직관적으로 쉽게 짤 수 있지만, O(n)이 되는 알고리즘을 짜는 것도 잘 공부해 두어야 한다. 대표적인 문제는 Leet Code 1456. Maximum umber of Vowels in a Substring of Given Length 이다.

 

Maximum Number of Vowels in a Substring of Given Length - LeetCode

구현 원리

 TC O(n)의 Sliding Window 알고리즘을 구현하기 위해선 Loop가 1번만 돌아가되, 인덱스 증가에 따라 tracking 하는 변수들을 선언하여 계산해나가면 된다. 즉, Loop를 순회하면서 새로운 인덱스의 값을 고려해 계산하고, 인덱스 증가에 따라 윈도우에서 벗어나게된 인덱스의 값 또한 고려하는 것이다. 여기선 정성적으로 설명했는데, 아래 예제 코드를 읽어보면 된다. 아래 코드는 위 Leet Code 1456. 에 제출한 답안이다.

class Solution {
public:
    int maxVowels(string s, int k) {
		int cnt = 0;
		int maxVow = 0;

		for (int i = 0; i != s.length(); ++i)
		{
			if (s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u')
			{
				++cnt;
			}
			else
			{
				// do Nothing
			}

			if (i >= k)
			{
				if (s[i - k] == 'a' || s[i - k] == 'e' || s[i - k] == 'i' || s[i - k] == 'o' || s[i - k] == 'u')
				{
					--cnt;
				}
				else
				{
					// Do Nothing
				}
			}
			else
			{
				// Do Nothing
			}

			maxVow = max(cnt, maxVow);

		}

		return maxVow;
    }
};