인터뷰 키트: 어레이 - 슬라이딩 윈도우.

패턴에 관한 모든 것!

패턴을 익히면 모든 것이 조금 더 쉬워집니다! 당신이 나와 같다면 아마도 기술 면접을 좋아하지 않을 것입니다. 당신을 비난하지는 않습니다. 면접이 어려울 수 있습니다.

어레이 문제는 인터뷰에서 접하게 되는 가장 일반적인 문제 중 일부입니다. 이러한 문제는 종종 자연 배열 작업과 관련됩니다.

const arr = [1, 2, 3, 4, 5];

그리고 본질적으로 문자 배열인 문자열 문제:

"mylongstring".split(""); // ['m', 'y', 'l', 'o','n', 'g', 's','t','r','i', 'n', 'g']

배열 문제를 해결하는 가장 일반적인 패턴 중 하나는 슬라이딩 윈도우입니다.

슬라이딩 윈도우 패턴

슬라이딩 창 패턴에는 마치 창이 어레이를 가로질러 미끄러지는 것처럼 같은 방향으로 움직이는 두 개의 포인터가 포함됩니다.

언제 사용해야 하는가

최소, 최대, 최장, 등 특정 조건을 만족하는 하위 배열이나 하위 문자열을 찾아야 할 때 슬라이딩 윈도우 패턴을 사용하세요. 가장 짧습니다.

규칙 1: 하위 배열이나 하위 문자열을 찾아야 하고 데이터 구조가 배열이나 문자열인 경우 슬라이딩 윈도우 패턴을 사용하는 것이 좋습니다.

간단한 예

다음은 슬라이딩 창의 포인터 개념을 소개하는 기본 예입니다.

function SlidingWindow(arr) {
    let l = 0;  // Left pointer
    let r = l + 1;  // Right pointer

    while (r < arr.length) {
        console.log("left", arr[l]);
        console.log("right", arr[r]);
        l++;
        r++;
    }
}

SlidingWindow([1, 2, 3, 4, 5, 6, 7, 8]);

왼쪽(L)과 오른쪽(R) 포인터는 동시에 움직일 필요는 없고 같은 방향으로 움직여야 한다는 점에 유의하세요.

오른쪽 포인터는 왼쪽 포인터보다 낮을 수 없습니다.

실제 면접 문제를 통해 이 개념을 살펴보겠습니다.

실제 문제: 반복되는 문자가 없는 가장 긴 부분 문자열

문제: 문자열 s가 주어졌을 때, 반복되는 문자가 없는 가장 긴 부분 문자열의 길이를 구하세요.

키워드: sub-문자열, 가장 길다(최대)

function longestSubstr(str) {
    let longest = 0;
    let left = 0;
    let hash = {};

    for (let right = 0; right < str.length; right++) {
        if (hash[str[right]] !== undefined && hash[str[right]] >= left) {
            left = hash[str[right]] + 1;
        }

        hash[str[right]] = right;
        longest = Math.max(longest, right - left + 1);
    }

    return longest;
}

복잡해 보이더라도 걱정하지 마세요. 차근차근 살펴보겠습니다.

let str = "helloworld";
console.log(longestSubstr(str));  // Output: 5

이 문제의 핵심은 반복되는 문자가 없는가장 긴 하위 문자열을 찾는 것입니다.

초기 창: 크기 0

처음에는 왼쪽(L)과 오른쪽(R) 포인터가 모두 같은 위치에 있습니다.

let left = 0;

for (let right = 0; right < str.length; right++) {  // RIGHT POINTER

h e l l o w o r l d 
^
^
L
R

빈 해시(객체)가 있습니다.

let hash = {};

물건의 좋은 점은 무엇인가요? 여기에는 이 문제를 해결하는 데 꼭 필요한 고유한 키가 저장됩니다. 해시를 사용하여 방문한 모든 문자를 추적하고 현재 문자를 이전에 본 적이 있는지 확인합니다(중복 감지).

문자열을 보면 문자 반복 없이 world가 가장 긴 하위 문자열임을 시각적으로 알 수 있습니다.

h e l l o w o r l d 
          ^        ^   
          L        R

길이가 5입니다. 그러면 어떻게 가나요?

단계별로 분석해 보겠습니다.

초기 상태

hash = {}

h e l l o w o r l d 
^
^
L
R

반복 1:

반복할 때마다 R 포인터 아래의 문자를 해시 맵에 추가하고 다음과 같이 증가합니다.

hash[str[right]] = right;
longest = Math.max(longest, right - left + 1);

현재 창에는 반복되는 문자(h 및 e)가 없습니다.

hash = {h: 0}
h e l l o w o r l d 
^ ^
L R

반복 2:

hash = {h: 0, e: 1}
h e l l o w o r l d 
^   ^
L   R

이제 새로운 창이 생겼습니다: hel.

반복 3:

hash = {h: 0, e: 1, l: 2}
h e l l o w o r l d 
^     ^
L     R

흥미로운 점은 다음과 같습니다. 해시에 이미 l이 있고 R은 문자열에서 다른 l을 가리키고 있습니다. 이것이 if 문이 들어오는 곳입니다:

if (hash[str[right]] !== undefined)

해시에 R이 가리키는 문자가 포함되어 있으면 중복된 문자를 찾은 것입니다! 이전 창(hel)이 지금까지 가장 길었습니다.

그럼 다음엔 뭘 할까요? 왼쪽 하위 문자열을 이미 처리했으므로 L 포인터를 위로 이동하여 왼쪽에서 창을 축소합니다. 그런데 L은 얼마나 이동할까요?

left = hash[str[right]] + 1;

L을 중복된 항목 바로 다음으로 이동합니다.

hash = {h: 0, e: 1, l: 2}
h e l l o w o r l d 
      ^
      ^
      L
      R

그래도 중복 항목을 해시에 추가하므로 이제 L의 인덱스는 3이 됩니다.

hash[str[right]] = right;
longest = Math.max(longest, right - left + 1);

새 상태: 반복 4

hash = {h: 0, e: 1, l: 3}
h e l l o w o r l d 
      ^ ^
      L R

반복 4~6

hash = {h: 0, e: 1, l: 3, o: 4, w: 5}
h e l l o w o r l d 
      ^     ^
      L     R

R이 또 다른 중복(o)을 가리키면 L을 첫 번째 o 바로 다음으로 이동합니다.

hash = {h: 0, e: 1, l: 3, o: 4, w: 5}
h e l l o w o r l d 
          ^ ^
          L R

다른 중복 l이 나타날 때까지 계속합니다.

hash = {h: 0, e: 1, l: 3, o: 4, w: 5, o: 6, r: 7}
h e l l o w o r l d 
          ^     ^
          L     R

하지만 현재 창 밖에 있다는 점에 주목하세요! w부터

규칙 3: 처리된 sub-x 무시

현재 기간 외의 내용은 관련이 없습니다. 이미 처리되었습니다. 이를 관리하는 핵심 코드는 다음과 같습니다.

if (hash[str[right]] !== undefined && hash[str[right]] >= left)

이 조건을 사용하면 현재 창 내의 문자에만 관심을 갖고 노이즈를 필터링할 수 있습니다.

hash[str[right]] >= left

왼쪽 포인터보다 크거나 같은 항목에 초점을 맞춥니다

최종 반복:

hash = {h: 0, e: 1, l: 8, o: 4, w: 5, o: 6, r: 7}
h e l l o w o r l d 
          ^       ^
          L       R

자세한 내용이라는 것은 알지만 문제를 더 작은 패턴이나 규칙으로 나누는 것이 문제를 마스터하는 가장 쉬운 방법입니다.

In Summary:

• Rule 1: Keywords in the problem (e.g., maximum, minimum) are clues. This problem is about finding the longest sub-string without repeating characters.
• Rule 2: If you need to find unique or non-repeating elements, think hash maps.
• Rule 3: Focus on the current window—anything outside of it is irrelevant.

Bonus Tips:

• Break down the problem and make it verbose using a small subset.
• When maximizing the current window, think about how to make it as long as possible. Conversely, when minimizing, think about how to make it as small as possible.

To wrap things up, here's a little challenge for you to try out! I’ll post my solution in the comments—it’s a great way to practice.

Problem 2: Sum Greater Than or Equal to Target

Given an array, find the smallest subarray with a sum equal to or greater than the target(my solution will be the first comment).

/**
 * 
 * @param {Array<number>} arr 
 * @param {number} target 
 * @returns {number} - length of the smallest subarray
 */
function greaterThanOrEqualSum(arr, target){
   let minimum = Infinity;
   let left = 0;
   let sum = 0;

   // Your sliding window logic here!
}

Remember, like anything in programming, repetition is key! Sliding window problems pop up all the time, so don’t hesitate to Google more examples and keep practicing.

I’m keeping this one short, but stay tuned—the next article will dive into the two-pointer pattern and recursion (prepping for tree problems). It’s going to be a bit more challenging!

If you want more exclusive content, you can follow me on Twitter or Ko-fi I'll be posting some extra stuff there!

Resources:

Tech interview Handbook

leet code arrays 101

위 내용은 인터뷰 키트: 어레이 - 슬라이딩 윈도우.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!