패턴에 관한 모든 것!

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

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

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 



왼쪽(L)과 오른쪽(R) 포인터는 동시에 움직일 필요는 없지만 같은 방향으로 움직여야 합니다.



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

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


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


문제: 문자열 s가 주어지면 반복되는 문자가 없는 가장 긴 하위 문자열의 길이를 찾습니다.

키워드: 하위-문자열, 가장 긴(최대)


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

    for (let right = 0; 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) 포인터가 모두 같은 위치에 있습니다.


왼쪽 = 0;

for (let right = 0; right let left = 0;

for (let right = 0; right h e l o w o r l d 
^
^
엘
아르 자형
h e l l o w o r l d 
^
^
L
R
그리고 빈 해시(객체)가 있습니다:


let hash = {};
h e l l o w o r l d 
^
^
L
R
객체의 장점은 무엇인가요? 고유한 
키를 저장하는데, 이것이 바로 이 문제를 해결하는 데 필요한 것입니다. 우리는 해시를 사용하여 우리가 방문한 모든 캐릭터를 추적하고 이전에 현재 캐릭터를 본 적이 있는지 확인합니다(중복을 감지하기 위해).

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


h e l o w o r l d 
          ^ ^   
          L R
h e l l o w o r l d 
^
^
L
R
길이는 5입니다. 그러면 어떻게 거기로 갈 수 있나요?


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



  
  
  초기 상태




해시 = {}

h e l o w or l d 
^
^
엘
아르 자형
h e l l o w o r l d 
^
^
L
R

  
  
  반복 1:


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


해시[str[right]] = 오른쪽;
maximum = Math.max(가장 길다, 오른쪽 - 왼쪽 1);
h e l l o w o r l d 
^
^
L
R
현재 창에는 반복되는 문자(h 및 e)가 없습니다.


해시 = {h: 0}
h e l o w or l d 
^ ^
L R
h e l l o w o r l d 
^
^
L
R

  
  
  반복 2:




해시 = {h: 0, e: 1}
h e l o w or l d 
^ ^
L R
h e l l o w o r l d 
^
^
L
R
이제 새 창이 hel 있습니다.



  
  
  반복 3:




해시 = {h: 0, e: 1, l: 2}
h e l o w or l d 
^ ^
L R
h e l l o w o r l d 
^
^
L
R
흥미로운 점은 다음과 같습니다. 해시에 이미 l이 있고 R은 문자열에서 다른 l을 가리키고 있습니다. 이것이 if 문이 들어오는 곳입니다:


if (hash[str[right]] !== 정의되지 않음)
h e l l o w o r l d 
^
^
L
R
해시에 R이 가리키는 문자가 포함되어 있으면 중복된 문자를 찾은 것입니다! 이전 창(hel)이 지금까지 가장 길었습니다.


그럼 다음엔 뭘 해야 할까요? 왼쪽 하위 문자열을 이미 처리했으므로 L 포인터를 위로 이동하여 왼쪽에서 창을 축소합니다. 하지만 L을 얼마나 멀리 이동시킬 수 있나요?


왼쪽 = 해시[str[오른쪽]] 1;
h e l l o w o r l d 
^
^
L
R
L을 중복된 항목 바로 다음으로 이동합니다.


해시 = {h: 0, e: 1, l: 2}
h e l o w or l d 
      ^
      ^
      엘
      아르 자형
h e l l o w o r l d 
^
^
L
R
우리는 여전히 해시에 중복 항목을 추가하므로 L은 이제 3의 인덱스를 갖게 됩니다.


해시[str[right]] = 오른쪽;
maximum = Math.max(가장 길다, 오른쪽 - 왼쪽 1);
h e l l o w o r l d 
^
^
L
R

  
  
  새 상태: 반복 4




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

  
  
  반복 4~6




해시 = {h: 0, e: 1, l: 3, o: 4, w: 5}
h e l o w or l d 
      ^ ^
      L R
h e l l o w o r l d 
^
^
L
R
R이 또 다른 중복(o)을 가리키면 L을 첫 번째 o 바로 다음으로 이동합니다.


해시 = {h: 0, e: 1, l: 3, o: 4, w: 5}
h e l o w or l d 
          ^ ^
          L R
h e l l o w o r l d 
^
^
L
R
다른 중복 l이 나타날 때까지 계속합니다.


해시 = {h: 0, e: 1, l: 3, o: 4, w: 5, o: 6, r: 7}
h e l o w or l d 
          ^ ^
          L R
h e l l o w o r l d 
^
^
L
R
하지만 현재 창 밖에 있다는 점에 주목하세요! w로 시작하는 



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


현재 창 밖의 내용은 관련이 없습니다. 이미 처리되었습니다. 이를 관리하는 키 코드는 다음과 같습니다.


if (hash[str[right]] !== 정의되지 않음 && hash[str[right]] >= 왼쪽)
h e l l o w o r l d 
^
^
L
R
이 조건을 사용하면 현재 창 내의 문자만 고려하여 모든 노이즈를 필터링할 수 있습니다.


해시[str[오른쪽]] >= 왼쪽
h e l l o w o r l d 
^
^
L
R
왼쪽 포인터보다 크거나 같은 항목에 초점을 맞춥니다.



  
  
  최종 반복:




해시 = {h: 0, e: 1, l: 8, o: 4, w: 5, o: 6, r: 7}
h e l o w or l d 
          ^ ^
          L R
h e l l o w o r l d 
^
^
L
R
자세한 내용이라는 것은 알지만 문제를 더 작은 패턴이나 규칙으로 나누는 것이 문제를 마스터하는 가장 쉬운 방법입니다.



  
  
  요약하면:

• 규칙 1: 문제의 키워드(예: 최대, 최소)는 단서입니다. 이 문제는 가장 긴 하위 문자열을 반복되는 문자 없이 찾는 문제입니다.
• 규칙 2: 고유하거나 반복되지 않는 요소를 찾아야 한다면 해시 맵을 생각해 보세요.
• 규칙 3: 현재 창에 집중하세요. 창 밖의 어떤 것도 관련이 없습니다.

보너스 팁:

작은 하위 집합을 사용하여 문제를 세분화하고 장황하게 만듭니다.
• 현재 창을 최대화할 때 어떻게 하면 최대한 길게 만들 수 있을지 고민해보세요. 반대로 최소화할 때는 어떻게 하면 최대한 작게 만들 수 있을지 고민해보세요.

마무리로 여러분이 시도해 볼 수 있는 작은 챌린지를 소개합니다! 제 솔루션을 댓글로 게시하겠습니다. 연습하기에 좋은 방법입니다.

문제 2: 합계가 목표보다 크거나 같음

배열이 주어지면 합계가 대상보다 크거나 같은 가장 작은 하위 배열을 찾습니다(내 솔루션이 첫 번째 주석이 됩니다).

/** * * @param {배열} arr * @param {숫자} 대상 * @returns {number} - 가장 작은 하위 배열의 길이 */ 함수 greatThanOrEqualSum(arr, target){ 최소 = 무한대라고 가정합니다. 왼쪽 = 0으로 두십시오. 합계 = 0으로 둡니다. // 슬라이딩 윈도우 로직이 여기에 있습니다! }

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

프로그래밍의 다른 모든 것과 마찬가지로 반복이 중요하다는 점을 기억하세요! 슬라이딩 윈도우 문제는 항상 발생하므로 주저하지 말고 Google에 더 많은 예제를 검색하고 계속 연습하세요.

이번 글은 짧게 유지하고 있지만 계속 지켜봐 주시기 바랍니다. 다음 글에서는 두 포인터 패턴과 재귀(트리 문제 준비)에 대해 자세히 알아볼 것입니다. 좀 더 어려울 거예요!

더 많은 독점 콘텐츠를 원하시면 Twitter나 Ko-fi에서 저를 팔로우하세요. 거기에 추가 콘텐츠를 게시하겠습니다!

자원:

기술 인터뷰 핸드북

leet 코드 배열 101