Minimum Window Substring

💬 문제

[문제 링크]

문자열 s의 부분 문자열 중
문자열 t의 각 문자가 모두 들어가는
가장 짧은 길이의 부분 문자열을 찾아 반환
t의 순서를 지키지 않아도 됨

✍️ 나의 풀이

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function(s, t) {
    let char = new Map();
    for (let i = 0; i < t.length; i++)
        char.set(t[i], char.has(t[i]) ? char.get(t[i]) + 1 : 1);

    let res = '';
    let cnt = char.size;
    let left = 0;
    let right = -1;
    while (right <= s.length) {
        if (cnt === 0) {
            let str = s.slice(left, right + 1);
            if (res === '')
                res = str;
            else
                res = res.length > str.length ? str : res;

            let temp = char.get(s[left]);
            if (temp !== undefined)
                char.set(s[left], temp + 1);
            if (temp + 1 > 0)
                cnt++;
            left++;
        } else {
            right++;
            let temp = char.get(s[right]);
            if (temp !== undefined)
                char.set(s[right], temp - 1);
            if (temp - 1 === 0)
                cnt--;
        }
    }

    return res;
};

우선 t의 각 문자를 map에 저장 (중복 문자가 있으면 값을 +1)
왼쪽과 오른쪽을 가리키는 포인터를 가지고 순회 시작
가장 처음에는 while 문 내에서 else 문으로 가기 때문에 설명은 그쪽부터
right을 증가하면서 창 크기를 늘림
만나는 인덱스 문자마다 map에 있는지 확인하고 그 개수인 값을 -1 하기
만약 값이 0이 되었다면 원하는 만큼 해당 문자가 포함된 것이므로 cnt를 -1
그렇게 cnt가 0이 되어서 t의 모든 문자가 창 내에 들어왔다면
현재 창만큼 문자열을 잘라서 res 값과 비교하여 더 짧은 것을 저장해두기
이후 창의 가장 앞쪽인 left가 가리키고 있는 문자를 창에서 제거
따라서 map에서는 해당 문자의 값을 다시 증가시키고, 중복이 없던 것이었으면 cnt도 증가
이렇게 모든 문자를 포함했을 때마다 창을 이동시키고 확인하여 늘리고를 반복

📌 결과

Accepted
Runtime 79ms (Beats 78.94%)
Memory 55.85MB (Beats 27.64%)

📚 러닝 포인트

솔직히 어려웠다. 슬라이딩 윈도우 알고리즘이라는 걸 생각하면서도 도저히 어떻게 해야할지 감이 안와서 힌트를 보았다. 힌트에서 거의 알고리즘을 다 알려주었는데도 구현을 어떻게 해야할지 모르겠어서 솔루션을 많이 참고했다. 코드 설명을 작성하면서는 이제 좀 쉽다고 생각이 들었지만 풀 때는 진짜 어려웠다. 이번에도 저번과 같이 찾아야할 것들을 map에 저장했다. 중간에 size를 변수에 담아야하는 곳이 있었는데 C++ 때의 버릇인지 size()라고 써서 런타임 에러가 났었다. 자바스크립트에서는 오브젝트 size도 배열 length도 메소드가 아니라 속성이라는 것을 잊지말자...