특정 원소가 모두 포함된 최소 슬라이딩 윈도우를 찾아보자 [LeetCode 76 / Java]

URL : https://leetcode.com/problems/minimum-window-substring/description/

LeetCode - The World's Leading Online Programming Learning Platform

 

 오늘은 특정 원소가 모두 포함되어 있는 최소 슬라이딩 윈도우를 찾는 방법을 알아보겠습니다! 특정 원소가 모두 포함된 최소 슬라이딩 윈도우가 무엇을 의미하는 것일까요? 잘 이해가 되지 않을 수가 있는데요, 문제를 통해 확인해 보도록 하겠습니다.

 

 문제 상황

 Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

The testcases will be generated such that the answer is unique.

Example 1:
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

 

Example 2:
Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.

 

Example 3:
Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.

 

 Example 1번을 보도록 하겠습니다. 2번 3번의 예는 너무 간단하니, 1번의 예를 살펴보도록 하겠습니다. 알고리즘 문제를 이해할 때 예시를 통해 이해하는 것이 정말 중요한데, 이 예시가 너무 간단하다면 오히려 알고리즘을 잘못 이해할 가능성이 있으니까요!

 

주어진 문자열 s = "ADOBECODEBANC" 그리고 t = "ABC"가 있습니다.

이 때, t라는 문자열 내에 'A' 'B' 'C'라는 알파벳이 있습니다.

우리의 목표는 문자열 s내에서, t에 존재하는 모든 알파벳이 포함 된 부분문자열(sliding window)을 찾는 것입니다. 슬라이딩 윈도우라는게 무엇인지 예를 한 번 들어보도록 하겠습니다.

 

"ADOBECODEBANC" → "ADOBE"

"ADOBECODEBANC" → "DOBECODEBA"

"ADOBECODEBANC" → "DEBANC"

"ADOBECODEBANC" → "BECODE"

 

 s문자열에서 슬라이딩 윈도우를 몇 개 뽑아 보았는데, 이 정도면 대충 감이 오실 것 같습니다. 그렇습니다. 문자열 내에서 슬라이딩 윈도우라는 것은 연속된 부분 문자열을 의미하는 것입니다. 우리는 이러한 슬라이딩 윈도우 중에서 주어진 조건을 만족하는, 즉 알파벳 'A' 'B' 'C'가 모두 포함된 슬라이딩 윈도우들을 찾고, 그 슬라이딩 윈도우 중에서 가장 짧은 것을 찾아내는 것이 목표라고 할 수 있습니다.

 

"ADOBECODEBANC" → "ADOBEC"

"ADOBECODEBANC" → " BANC " → 정답!!

"ADOBECODEBANC" → " CODEBANC "

 

 알파벳 A B C를 포함하는 슬라이딩 윈도우는 정말 많습니다. 그 중에서 가장 짧은 슬라이딩 윈도우인 "BANC"가 바로 우리가 찾는 최종 목표가 되겠습니다! 문제 해결 목표가 무엇인지 감이 오시나요?

 그러면, 주어진 문자열 내에서 가장 짧은 슬라이딩 윈도우를 어떻게 하면 찾아낼 수 있을까요? 슬라이딩 윈도우 알고리즘을 사용하면 됩니다.

 

 아, 헷갈리실 수도 있겠는데요, 위에서 제가 빨간색으로 강조한 슬라이딩 윈도우 알고리즘이라는 것은,  이 문제에서 의미하는 슬라이딩 윈도우가 아닌, 알고리즘 전반에서 범용적으로 사용하는 문제 해결 방법인 '슬라이딩 윈도우 해법'을 일컫는 말입니다! 왼쪽에 포인터 하나, 오른 쪽에 포인터 하나를 두게 되는데, 이 두 포인터 구간을 윈도우 라고 합니다. 그리고 이 윈도우를 움직이며, 크기를 변화시켜 가면서 연산을 진행하는 것이 바로 슬라이딩 윈도우 알고리즘 이라고 할 수 있습니다.

 

 아이디어

 슬라이딩 윈도우를 통해 어떻게 최소 부분 문자열을 찾아낼 수 있는 지, 큰그림을 그려보도록 합시다!

 가장 먼저, 문자열 내의 첫 글자를 포함하는 윈도우를 하나 만듭니다. 이 윈도우가 어떻게 구현되는 지는 나중에 코드로 구현할 것입니다. 일단 슬라이딩 윈도우를 그림과 같이 만드는 작업을 한다고만 이해합시다!

 

 

그리고, 윈도우의 오른쪽 끝을 하나씩 늘려가면서, 문제에서 주어진 조건에 부합하는 지, 즉 우리가 설정한 슬라이딩 윈도우 내에 알파벳 'A' 'B' 'C'가 포함되어 있는 지를 판단합니다. 슬라이딩 윈도우의 오른쪽 끝을 언제까지 계속 확장시켜 나갈까요? 바로, 알파벳 'A' 'B' 'C'가 슬라이딩 윈도우에 모두 포함이 될 때 까지 오른쪽 끝을 확장 시켜 나가는 것입니다.

 

 슬라이딩 윈도우의 오른쪽 끝을 확장시켜 나가다가 보니, 슬라이딩 윈도우 내에 알파벳 'A' 'B' 'C'가 모두 존재하는 것을 볼 수가 있습니다. 주어진 조건을 만족하는 슬라이딩 윈도우를 찾았으니, 일단 이것을 기록해야겠지요? 물론, 나중에 조건을 만족하는 더 짧은 슬라이드가 나온다면 이것이 아닌,그것을 정답으로 반환해야 하지만요. 

 

 이렇게 슬라이딩 윈도우내에 알파벳 'A' 'B' 'C'가 모두 존재할 때 우리는 어떤 작업을 할 수가 있을까요? 우리의 목표는 주오진 조건을 만족하는 가장 짧은 슬라이딩 윈도우를 찾는 것입니다. 

 

"조건을 만족하는 슬라이딩 윈도우의 왼 쪽 경계를 오른쪽으로 한 번 한 번 옮겨보자. 한 번씩 옮길 때마다, 옮긴 후에도 해당 윈도우가 조건을 만족하는 지를 확인하자."

 

 주어진 조건을 만족하는 슬라이딩 윈도우를 찾는다면, 왼 쪽 경계를 오른쪽으로 이동 시켜 가면서, 조건을 만족하는 더욱 짧은 슬라이딩 윈도우를 찾습니다.

 

 왼 쪽 경계를 하나 하나 옮기면서, 해당 윈도우가 주어진 조건을 만족하는 지를 확인합니다. 만약 조건에 부합하지 못하는 경우, 아까 했던 것처럼 오른 쪽 경계를 이동시켜 가는 작업을 반복합니다.

 

슬라이딩 윈도우를 확장시켜 나가다가, 또 주어진 조건을 부합한다면 슬라이딩 윈도우의 왼쪽 경계를 오른쪽으로 이동시켜 가면서 더욱 짧은 슬라이딩 윈도우를 찾습니다.

 

계속 슬라이딩 윈도우 크기를 줄여가면서 확인합니다.

 

 

 

 왼 쪽 경계를 하나 하나 옮기면서, 해당 윈도우가 주어진 조건을 만족하는 지를 확인합니다. 만약 조건에 부합하지 못하는 경우, 아까 했던 것처럼 오른 쪽 경계를 이동시켜 가는 작업을 반복합니다.

 

 

 슬라이딩 윈도우를 확장시켜 나가다가, 또 주어진 조건을 부합한다면 슬라이딩 윈도우의 왼쪽 경계를 오른쪽으로 이동시켜 가면서 더욱 짧은 슬라이딩 윈도우를 찾습니다.

 

계속 슬라이딩 윈도우 크기를 줄여가면서 확인합니다.

 

 

 

이런 식으로 동작하는 슬라이딩 윈도우를 통해 주어진 알파벳이 모두 포함된 최소 부분 문자열을 찾아낼 수가 있는 것입니다.

 

 

소스 코드

 

 소스코드를 보기 전에 동작 원리를 알면 확실히 이해하기가 넘사벽으로 쉬워집니다. 슬라이딩 윈도우를 확장 또는 축소시켜 나가면서 우리는 "현재 윈도우 내에 필수 알파벳들이 모두 포함이 되어 있는가?"를 확인한다고 했습니다. 이 확인하는 작업을 상수 시간 복잡도 O(1) 내로 처리해야만 전체 시간복잡도가 O(N)이 됩니다. 이 작업을 위해서 required라는 변수가 사용이 되는 것입니다.

 

class Solution {
    public String minWindow(String s, String t) {
    
        int[] count = new int[128];
        int start = 0;	// 최소 윈도우를 만날 때마다 해당 윈도우의 시작점을 기록!
        int minLength = s.length() + 1; // 최소 윈도우를 만날 때마다 해당 윈도우의 길이를 기록!
        int required = t.length();

	// 반드시 포함되어야 하는 알파벳으로 이루어진 문자열 t를 통해서
        // 반드시 필요한 알파벳과 필요 개수를 센다.
        for(char ch : t.toCharArray()){
            count[ch]++;
        }

        for(int l = 0, r = 0; r < s.length(); r++) {
            // 슬라이딩 윈도우의 오른쪽을 증가시켜 가면서 크기를 키운다.
            count[s.charAt(r)]--;
            
            // 만약 방금 윈도우가 확장되면서 추가된 알파벳이, 
            // '윈도우 내에 반드시 포함되어야 하는 알파벳'이라면
            if(count[s.charAt(r)] >= 0)
                required--;
            
            // 현재 슬라이딩 윈도우 내에 모든 문자가 포함되었다면
            while(required == 0) {
            
            	// 현재 슬라이딩 윈도우를 기록한다!
                if(minLength > r - l + 1) {
                    minLength = r - l + 1;
                    start = l;
                }
                
                // 슬라이딩 윈도우의 왼쪽을 축소시켜 가며 최소 길이를 찾는다
                count[s.charAt(l)]++;
                
                // 만약 우리가 반드시 포함해야 하는 알파벳이 나가 떨어졌다면,
                if(count[s.charAt(l)] > 0)
                    required++;
                l++;
            }

        }

        return minLength == s.length() + 1 ? "" : s.substring(start, start + minLength); 
    }
}

 

※ required 변수의 의미 :

 

"슬라이딩 윈도우 내에 반드시 포함되어야 하는 알파벳 중에서 몇 개가 아직 포함되지 않았는가"

 

count라는 정수형 배열에는 각 알파벳에 다음 값을 대응시킬 예정입니다.

 

"각 알파벳이 얼만큼 더 슬라이딩 윈도우 내에 포함이 되어야 하는가"

 

그래서 처음으로 count배열은 다음과 같이 초기화가 되면서 시작됩니다.

 

 슬라이딩 윈도우가 확장되면, count배열에서 확장되면서 포함된 알파벳에 해당하는 값을 하나씩 감소시켜줍니다.

 

 

 가장 처음으로 첫 원소를 포함시키는 슬라이딩 윈도우를 만든다고 하였죠? 이렇게 되면, 슬라이딩 윈도우 내에 A라는 알파벳이 포함이 되므로 count배열의 'A'인덱스의 값이 하나 깎여져 나갑니다. 깎여져 나간 후, 'A'인덱스에 해당하는 값이 1에서 0으로 감소한 것을 볼 수가 있죠. 이 때, 깎여져 나간 후 값이 0보다 크다면! 다음과 같이 판단을 하고 required값을 하나 감소시킵니다.

 

"우리가 슬라이딩 윈도우 내에 반드시 포함시켜야 하는 문자가 들어왔다"

 

 반대로, 슬라이딩 윈도우가 축소되면서 삭제된 알파벳에 해당하는 인덱스가 1 이상이라면, 

 

"우리가 슬라이딩 윈도우 내에 반드시 포함시켜야 하는 문자가 나가 떨어졌다"

 

라고 판단하며 required값을 하나 증가시킵니다.

이런 식으로 하다 보면 슬라이딩 윈도우 내에 우리가 필요로 하는 모든 알파벳이 들어가 있을 시 required값이 0이 되는데, if(required == 0)구문을 통해서 아, 슬라이딩 윈도우 내에 우리가 반드시 포함해야 하는 알파벳들이 잘 들어있구나! 하고 알 수 있는 것입니다.