Sliding Window 대표 문제 풀기

이번 포스트에서는 Sliding Window와 관련된 문제를 풀어보겠습니다.

 

풀이는 코드에 직접 적었습니다.

혹시나 궁금하신 부분이 있으시면 댓글로 문의 부탁드립니다.

 

1. Best Time to Buy and Sell Stock

Best Time to Buy and Sell Stock - LeetCode

풀이

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        
        // 이전에 나온 최솟값을 저장하는 변수를 정의합니다.
        // 최솟값에 사서 현재값이 팔면 이익이 나오는데 그 이익의 최대를 구하면 됩니다.
        int ans = 0, min_value = prices[0];
        
        // 배열의 길이가 최소 1이기 때문에 1부터 시작하실 수 있습니다.
        for (int i = 1; i < (int)prices.size(); ++i) {
            // 이전의 최솟값에 사서, 현재값이 팔아 이익을 구하고, 그 값을 최댓값과 비교합니다.
            ans = max(ans, prices[i] - min_value);
            
            // 최솟값을 업데이트합니다.
            min_value = min(min_value, prices[i]);
        }
        
        return ans;
    }
};

 

2. Longest Substring Without Repeating Characters

Longest Substring Without Repeating Characters - LeetCode

풀이

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        const int n = (int)s.length();
        
        // substring의 시작을 가리키는 포인터를 정의합니다.
        int start = 0;
        
        // substring에 들어있는 문자 중복을 체크하기 위해서 해시맵을 정의합니다.
        unordered_map<char, int> count;
        
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            // 현재 문자를 substring에 추가합니다.
            count[s[i]]++;
            
            // 만약 현재의 알파벳이 이전에 나왔으면
            // 그 알파벳이 사라질때까지 시작 포인터를 움직여서 substring에서 제외시킵니다.
            while(count[s[i]] > 1) {
                count[s[start]]--;
                start++;
            }
            
            // substring의 길이와 최댓값을 비교합니다.
            ans = max(ans, i - start + 1);
        }
        
        return ans;
    }
};

 

 

3. Longest Repeating Character Replacement

Longest Repeating Character Replacement - LeetCode

풀이

class Solution {
public:
    
    bool valid(vector<int> & count, int k) {
        // 최빈값과 전체 길이를 구합니다.
        int max_val = 0;
        int total = 0;
        for (auto &x:count) {
            max_val = max(max_val, x);
            total += x;
        }
        
        // 최빈값을 제외한 문자의 개수가 K보다 작거나 같으면 true, 아니면 false 입니다.
        return total - max_val <= k;
    }
    
    int characterReplacement(string s, int k) {
        
        // Sliding window 안에 들어있는 문자의 수를 저장하기 위한 배열을 정의합니다.
        vector<int> count(26, 0);
        
        
        // Substring의 시작지점을 가리키는 변수를 지정합니다.
        int start = 0, ans = 0;
        
        // 배열을 순회하면서 가장 자주 나온 문자열을 제외한 문자들의 수가 K보다 작은지를 확인합니다.
        // 만약 크다면, start를 옮겨서 Substring 길이를 줄여야 합니다.
        for (int i = 0; i < (int)s.length(); ++i) {
            count[s[i] - 'A']++;
            
            // valid() 함수는 K번으로 바꿀 수 있는지 확인합니다.
            if (!valid(count, k)) {
                count[s[start]-'A']--;
                start++;
            }
            
            // 반드시 valid한 경우만 나오기 때문에, 최댓값을 바로 비교하면 됩니다.
            ans = max(ans, i - start + 1);
        }
        
        return ans;
    }
};

 

 

4. Minimum Window Substring

Minimum Window Substring - LeetCode

풀이

class Solution {
public:
    bool canReduce(vector<vector<int>> & count, vector<vector<int>> & target_count, char & c) {
        // 만약 start 문자가 t에 있는 수보다 크면 불필요한 값이므로 줄일 수 있습니다. 
        if (c >= 'A' && c <='Z') {
            if (count[0][c -'A'] > target_count[0][c-'A']) {
                return true;
            }
        } else {
            if (count[1][c -'a'] > target_count[1][c-'a']) {
                return true;
            }
        }
        return false;
    }
    
    bool valid(vector<vector<int>> & count, vector<vector<int>> & target_count) {
        
        // 두 배열을 비교해야 하는데, target_count를 기준으로 비교합니다.
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 26; ++j) {
                // target_count의 값이 0인 것은 고려할 필요가 없습니다.
                // 왜냐하면 target_count에 있는 문자구성만 들어있으면 되고, 
                // 그 외 문자는 언제든 들어갈 수 있기 때문입니다.
                if (target_count[i][j] > 0 && target_count[i][j] > count[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }
    
    string minWindow(string s, string t) {
        // t에 들어있는 문자구성을 저장합니다.
        vector<vector<int>> target_count(2, vector<int> (26, 0));
        for (auto &x:t) {
            // uppercase는 [0] 번째에 저장합니다.
            if (x >= 'A' && x <= 'Z') {
                target_count[0][x - 'A']++;
            } 
            // lowercase는 [1] 번째에 저장합니다.
            else {
                target_count[1][x - 'a']++;
            }
        }
        
        
        int start = 0, min_val = 1e9;
        string ans = "";
        
        // substring에 들어갈 문자구성을 저장하는 배열을 생성합니다.
        vector<vector<int>> count(2, vector<int>(26, 0));
        for (int i = 0; i < (int)s.length(); ++i) {
            
            // 현재 문자를 배열에 저장합니다. -> 윈도우를 증가합니다.
            if (s[i] >= 'A' && s[i] <= 'Z') {
                count[0][s[i]-'A']++;
            } else {
                count[1][s[i]-'a']++;
            }
            
            // 줄일 수 있는지 체크합니다.
            while(start < i && canReduce(count, target_count, s[start])) {
                if (s[start] >= 'A' & s[start] <= 'Z') {
                    count[0][s[start] - 'A']--;
                } else {
                    count[1][s[start] - 'a']--;
                }
                start++;
            }
            
            // valid한지 확인합니다.
            if (valid(count, target_count) && min_val > i - start + 1) {
                min_val = i - start + 1;
                ans = s.substr(start, i - start + 1);
            }
        }
        
        
        return ans;
    }
};

 

Sliding Window 문제는 전반적으로 Two pointers와 비슷한 느낌이 있습니다. 하지만 다른 점은 Sliding Window의 경우 시작과 끝의 사이값들을 모두 tracking하는 경우가 많습니다. 그래서 주로 조건에 맞는 subarray 또는 substring을 구할 때 자주 사용합니다. 문제를 풀 때 Sliding Window를 사용해야겠다는 생각이 드셨다면, 어떤 조건에서 Window를 조절할지 고민해보시는 것이 좋습니다.

 

---

 

Sliding Window와 비슷한 Two pointers 패턴 문제들도 한 번 풀어보시기 바랍니다 :)

Two pointers 대표 문제 풀기

 

Best Time to Buy and Sell Stock 시리즈 문제를 더 풀어보고 싶으신 분들은 아래 포스트도 한 번 보시는 것을 추천드립니다.

Best Time to Buy and Sell Stock