[리트코드] 76. Minimum Window Substring (슬라이딩 윈도우)

문제 :

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

Minimum Window Substring - LeetCode

 

난이도 : hard

 

풀이 알고리즘 : sliding window(슬라이딩 윈도우)

 

⭐️ 슬라이딩 윈도우란 ? 

일정 범위 만큼의 윈도우(w)를 가지고 슬라이딩 ~ 하며 찾는 기법을 말합니다. 

주로 구간 문제에 많이 사용되며 투포인터와 방법론이 비슷하여 같이 얘기 됩니다.

 

하지만 투포인터는 2개의 포인터(left, right)를 가지고 구간의 길이가 다이나믹하게 움직일 수 있지만 슬라이딩 윈도우의 경우 서브 배열의 길이가 항상 일정하다는 점에서 다른 매력점을 가집니다.

바로 바로

 

🟨🟨🟨 윈도우의 길이가 w = 3 만큼 고정되어 간다 했을 때 

 ⬛️⬛️🟨🟨🟨⬛️⬛️⬛️ -> ⬛️⬛️🟥🟨🟨🟩⬛️⬛️ 

새로운 서브 배열은 🟨🟨🟩 가 될 것입니다. 

이때 🟨🟨는 중복 사용되므로 w-1 만큼은 재사용 하며 🟩은 더하고 🟥는 빼주며 O(1)시간만큼 새로운 🟨🟨🟩 값을 구할 수 있습니다. 

 

그래서 서브 스트링이 구간을 도는데 O(n) 만큼의 시간 복잡도를 가집니다. 

 

문제를 스스론 풀지 못했고 좋은 기법인거 같아서 다음에 잘 이용하려고 메모합니다 ...

 

---

s_len만큼 돌면서 letters[s[high]]가 0보다 큰 값만 count를 증가시켜 구간의 길이를 정한다.

 

high - low 구간 길이 만큼의 서브 배열에 t 문자들이 다 포함되었을 시 low값을 앞으로 옮겨 최소한의 길이로 줄이고 min_length에 저장한다. low를 옮길 수 있는 조건은 letters map의 값이 0보다 작은 경우!

 

t에 없는 문자들은 초기 값이 0이었기 때문에 count 값이 t 길이와 같아지기 전에 이미 하나씩 줄어들었기 때문에 무조권 -1, -2 등 상관 없이 0보다 작은 값일 것

 

t 문자 중 서브 배열에 중복된 문자가 있을 경우도 마찬가지로 window의 범위에서 줄여야 하는데 중복된 값은 t에 없는 문자처럼 값이 < 0 으로 만들어지기 때문에 window의 양 끝값에 t 문자열이 있는 최소한의 window substring을 만들 수 있다.  

 

 

 

c++ 코드 :

class Solution {
public:
   string minWindow(string s, string t) {
   	int t_len = t.length();
        int s_len = s.length();
        int maxInt = 2147483647;
        
        unordered_map<char, int> letters; // t 문자가 s에 있는지 확인하기 위한 map ex> A : 1, B : -1, C : -2 ...
        for(int i =0; i < t_len; i++){
           letters[t[i]]++; 
        }
        
        int count = 0; //t 문자열 서브 배열에 충족 시
        int low = 0, min_length = maxInt, min_start = 0;    
       
       
        for(int high = 0; high < s_len; high++) {
        
            if(letters[s[high]] > 0) {
                count++; //means that this letter is in t  
            }
            
            letters[s[high]]--; 

            if(count == t_len) { //조건 충족
                while(low < high && letters[s[low]] < 0) {
                    cout << letters[s[low]] <<'\n';
                    letters[s[low]]++;
                    low++; 
                }
                
                if(maxInt > high-low) {
                    min_length = high - (min_start = low) + 1; 
                }
                
                letters[s[low++]]++; //low 업데이트 전 문자 값 증가
                count--;
            }
        }
        return min_length == maxInt ? "" : s.substr(min_start, min_length); 
    }
};

 

전에 스터디 언니가 카카오 보석 쇼핑 문제도 슬라이딩 윈도우를 사용해 풀면 좋은 문제라 알려줬는데 함 풀어봐야겠다.