🔴[Leet code - 76] Minimum Window Substring ❌✅

Minimum Window Substring - LeetCode

문제

• Input
  문자열 s, t
• Output
  t의 모든 문자가 포함된 s의 부분 문자열중 최소 길이를 가진 문자열, 존재하지 않으면 ""반환
• Constraints
  정답이 유일하고, 문자열은 알파벳 소문자 아니면 대문자를 가진다.

 

시간 복잡도

※1초에 1억 번을 대략적인 기준으로 삼는다.

| O(1) : 크게 상관 없음 | O(log n) : 크게  상관 없음 | O(n) :  100'000'000 (1억) | O(n log n) : 1'000'000 (100만) | O(n^2) : 10'000 (1만) |

---

 

$1 \le s.size, t.size \le 100'000$이기 때문에, 대략 n log n부터 고려가능하다.

 

 

해결 과정

연속된 문자열과 그 구간에서의 조건 만족에 대한 알고리즘은 슬라이딩 윈도우를 우선으로 고려해볼 수 있다.
특히 조건을 만족하는 구간의 최소, 최대, 최단, 최장 이런 값들을 구하는거에는 특화되어있기 때문에 문제에 적합하다고 생각했다.

 

대략 아래와 같은 순서를 생각했다.

FOR (0 <= R < n)
{
    R 이동

    WHILE (포함된다면)
    {
        L 이동
    }

    // 여기 들어오는 WINDOW의 길이에 + 1을 하면 현재 R이 마지막이 되는 최소길이가 나온다.
    답 후보 갱신
}

해당 로직은 투포인터로 $O(2n)$의 복잡도를 가지기 때문에 충분히 통과가능한 시간을 가진다.

 

이제 중요한 건 부분 문자열에 t가 포함 되는지를 어떻게 확인할지가 문제였다. 제일 간단한 건 알파벳을 인덱스로 사용하는 정적 배열을 만들어 윈도우와 t의 빈도수를 매번 전부 비교하는 방법인데, 이 방식은 필요 없는 문자까지 계속 확인해야 하므로 굉장히 비효율적으로 느껴졌다. 그래서 t에 속한 문자만 확인 가능한 방법을 생각했었다.

 

t의 문자 빈도수를 저장하는 need, 현재 윈도우의 문자 빈도수를 저장하는 window 두 배열을 따로 두기로 했다.

이때, 어떤 문자 c가 있다면 아래와 같이 확인해볼 수 있다.

• need[c] > 0 이면 t에 필요한 문자이고
• window[c] == need[c] 가 되는 순간, 해당 문자 조건이 충족되었다고 볼 수 있다.

이 방법은 특정 문자 하나가 만족됐는지 확인하는 방법이기 때문에 이 방법만으로는 window에 t가 포함되는지 알 수 없다.

그래서 여기에 더하여, t에 사용된 문자개수를 따로 저장하여 해당 값만큼 충족이 되는지 확인하였다.

 

 

구현

string minWindow(string s, string t) 
    {
        int wTable[130] = {0}; // 부분문자열 빈도수 체크
        int tTable[130] = {0}; // t 문자열 빈도수 체크
        for (char c : t)
        {
            ++tTable[c];
        }


        int tCnt = 0; // t에서 사용된 알파벳 개수
        for (int i : tTable)
        {
            if (0 < i) ++tCnt;
        }


        int retL = 0;        // 유력한 답 후보의 L인덱스
        int retLength = INT_MAX;   // 유력한 답 후보의 길이

        int l = 0;
        for (int r = 0; r < s.size(); ++r)
        {
            char R = s[r];
            if (0 < tTable[R] && ++wTable[R] == tTable[R])
            {
                tCnt -= 1;
            }

            while (tCnt == 0)
            {   

                int nowLength = r - l + 1;

                if (nowLength < retLength)
                {
                    retL = l;
                    retLength = nowLength;
                }

                char L = s[l];

                // 이동하기전에 기존 L의 문자를 체크해제
                if (0 < tTable[L] && --wTable[L] < tTable[L])
                {
                    tCnt += 1;
                }
                
                // L 이동
                l++;
            }   
        }
        
        return retLength == INT_MAX ? "" : s.substr(retL, retLength);
    }

 

 

이전 풀이

해결 과정

핵심 로직을 떠올리는데까지는 시간이 오래 걸리지 않았으나, 디테일한 부분에서 구현하지 못했다.

핵심 로직은 슬라이딩 윈도우를 사용한 방법으로 아래와 같다.

1. 일단 투포인터 사용하여, 윈도우(부분문자열)가 t를 포함할 때까지 Right를 움직인다.
2. 포함하게 되는 순간, Left를 줄일 수 있는 만큼 줄인다.
3. Right가 s.size만큼 이동할때까지 반복한다.

여기서 가장 고민했던 부분은 현재 윈도우(부분 문자열)가 t를 포함하는지에 대한 방법을 고민했었다.

이번 문제에서는 윈도우에 t 이외의 문자도 포함이 가능했었기에 이전처럼 윈도우 길이나 문자 종류만으로는 조건을 판단할 수 없었다.

 

처음에는 int table[127] 같은 배열에 t의 문자 빈도수를 저장하여 순회하려고 보니, 너무 필요 없는 원소까지도 본다는 생각에 어떻게 최적화를 해야 하는지에 대해 시간을 많이 소요했다.

 

투포인터다 보니 포인터들이 가리키는 원소만 검사하면 된다는 생각도 있었지만, 그 외의 원소들이 조건에 적합한지에 대한 확신을 갖는 식은 떠올리지 못했다.

 

결국 스스로 방법에 도달하지는 못했지만 방법은 아래와 같다.

(0 < table[char] && table[char] == window[char]) 같은 조건문으로 간단하게 검사가 가능했고,

해당 조건문과 t와 적합한지에 대한 카운트를 따로 두어 알고리즘을 완성시킬 수 있었다.

 

 

구현

string minWindow(string s, string t) 
{
    int need[128] = {0};
    int window[128] = {0};

    for (char c : t)
        need[(unsigned char)c]++;

    int formed = 0;
    int required = 0;
    for (int x : need)
        if (x > 0) required++;

    int bestL = 0;
    int bestLen = INT_MAX;

    int left = 0;
    for (int right = 0; right < (int)s.size(); ++right) {
        unsigned char c = (unsigned char)s[right];
        window[c]++;

        if (need[c] > 0 && window[c] == need[c])
            formed++;

        while (formed == required) {
            if (right - left + 1 < bestLen) {
                bestLen = right - left + 1;
                bestL = left;
            }

            unsigned char d = (unsigned char)s[left];
            if (need[d] > 0 && window[d] == need[d])
                formed--;

            window[d]--;
            left++;
        }
    }

    return bestLen == INT_MAX ? "" : s.substr(bestL, bestLen);
}

 

 

되돌아보기

조건 충족 여부를 상태값으로

현재 윈도우가 t를 포함하는지를 매번 직접 비교하지 않고,
조건 충족 여부를 상태값으로 관리하여 더 빠르게 검사를 시도할 수 있었다..!

이번 문제에서는 need와 window를 같은 두 개의 빈도 배열을 따로 두고, 현재 필요한 문자 종류 중 몇 개가 충족되었는지를 관리하여 전체를 반복해서 비교하지 않고도 윈도의 유효성을 판단할 수 있었다.

그래서 다음에 슬라이딩 윈도우 문제를 풀 때, 현재 구간이 유효한지 판단하는 조건을 어떻게 줄일지,
유효해진 이후에는 확장할지 압축할지를 먼저 구분해서 생각해 볼 수 있을 것 같다.

 

구간의 저장 방식

구간을 저장할때 보통 왼쪽과 오른쪽 인덱스를 가지고 있었는데,

이번에는 그렇게 저장하면, 좀 어렵게 저장하는 듯한 느낌이 있다.

 

그래서 구현 코드에서는 시작점과 길이를 저장하였는데, 이 방법이 좀 더 안전하다고 생각했다.

1. 답을 찾지 못했다는 의미
   답이 존재하지 않는 게 답인 문제에서는 왼쪽과 오른쪽 포인터로만은 의미를 표현하기 힘들어 bool 같은 변수를 따로 두어 체킹을 해야 한다. 이걸 길이로 표현한다면 초기 값으로 INT_MAX 같은 값을 두어 쉽게 해당 문제의 답을 반환할 수 있다.
2. 답 반환
   애시당초 substr에서 길이를 매개변수로 받고 있으니, 당연하게도 더 깔끔하게 답을 반환할 수 있다.