Sliding Window

sliding window라는 알고리즘에 대해 알아봅시다. 창문이 옮겨간다는 이 알고리즘 풀이 방식은 범위(창문)가 자동으로 옮겨가면서 조건에 해당하는 답을 반환하게 됩니다. 이 방법 또한 마찬가지로 시간복잡도가 O(n)이며, 자주 활용되는 방식입니다.

1. maxSubarraySum

maxSubarraySum([100, 200, 300, 400], 2); // 700
maxSubarraySum([1, 4, 2, 10, 23, 3, 1, 0, 20], 4); // 39
maxSubarraySum([-3, 4, 0, -2, 6, -1], 2); // 5
maxSubarraySum([2, 3], 3); // null

maxSubarraySum은 배열과 숫자, 두 개의 인수로 숫자에 해당하는 길이의 subarray의 총합이 가장 큰 배열을 찾아내는 알고리즘 문제입니다.

Solution (1) - sliding window

function maxSubarraySum(arr, num) {
  let maxSum = 0;
  let tempSum = 0;
  if (arr.length < num) return null;

  for (let i = 0; i < num; i++) {
    maxSum += arr[i];
  }
  tempSum = maxSum;

  for (let i = num; i < arr.length; i++) {
    tempSum = tempSum + arr[i] - arr[i - num];
    maxSum = Math.max(tempSum, maxSum);
  }
  return maxSum;
}

먼저 두 개의 변수를 지정해줍니다. 일시적인 합(tempSum) 그리고 가장 큰 합(maxSum)이 그것입니다. 마지막엔 두 값을 비교하여 maxSum을 반환하게 됩니다.

이를 풀이하는 방식으로 첫 번째 반복문을 통해 arr[0]부터 시작하여 num의 숫자만큼까지의 배열 값의 총합을 계산합니다.

두 번째 반복문이 중요한데 여기서 sliding window라는 개념이 등장합니다. 반복문을 통해 범위를 이동시키면서 원래 있던 범위의 뒤에 있는 값을 더하고 맨 앞에 있는 값을 빼는 방식입니다.

예를 들어, [100, 200, 300, 400]의 첫 값이 [100, 200]이라면 여기서 다음 범위의 합은 300을 더하고 100을 빼는 것입니다. 이것이 arr[i]와 arr[i - num]을 통해 구현하게 되는 로직입니다.

저도 처음 봤을 때에는 이해하기 어려웠지만, 반복해서 문제를 풀이해보면서 개념에 익숙해질 수 있었습니다. 하지만 응용 문제가 나오면 풀이는 여전히 쉽지가 않아서 관련하여 많은 문제를 풀어보려 합니다.

2. findLongestSubstring

findLongestSubstring(""); // 0
findLongestSubstring("rithmschool"); // 7
findLongestSubstring("thisisawesome"); // 6
findLongestSubstring("thecatinthehat"); // 7
findLongestSubstring("bbbbbb"); // 1
findLongestSubstring("longestsubstring"); // 8
findLongestSubstring("thisisshowwedoit"); // 6

이번에는 substring 문제입니다. 가장 긴 substring으로 중복되는 알파벳이 없는 가장 긴 substring의 길이를 반환하는 알고리즘입니다.

Solution (1) - sliding window

function findLongestSubstring(str) {
  let longest = 0;
  let seen = {};
  let start = 0;

  for (let i = 0; i < str.length; i++) {
    let char = str[i];
    if (seen[char]) {
      start = Math.max(start, seen[char]);
    }

    longest = Math.max(longest, i - start + 1);
    seen[char] = i + 1;
  }
  return longest;
}

해당 문제는 하루 정도의 시간을 갖고 고민한 문제였지만, 풀이를 할 수 없었습니다. 하루 정도의 시간을 갖고도 풀 수 없다면, 결국 풀 수 없다 생각하기 때문에 풀이 답안을 보고 블로그에 정리하여 익숙해지는 방식을 택했습니다.

findLongestSubstring("school");

1-1. let char = str[0]; // "s"
먼저, str[0]에 해당하는 "r"을 변수 char에 할당합니다.

1-2. if(seen["s"]) { start = Math.max(start, seen["s"]); }
seen이라는 객체에 "s"이라는 키 값이 있다면, 뒤의 내용을 실행하지만 현재에는 없기 때문에 바로 아래 있는 내용으로 넘어갑니다.

1-3. longest = Math.max(longest, i - start + 1);
longest에 뒤의 값을 할당합니다. 여기서 Math.max(0, 0 - 0 + 1)으로 longest에 1을 할당하게 됩니다.

1-4. seen[char] = i + 1;
seen["s"]의 value는 여기서 0+1로 1이 됩니다.

2-1. let char = str[1]; // "c"

2-2. longest = Math.max(longest, i - start + 1);
longest는 현재 1이고 Math.max(1, 1 - 0 + 1)로 2가 할당됩니다.

2-3. seen["c"] = i + 1;
seen["c"]의 value는 2가 할당됩니다.

3-1. let char = str[2]; // "h"

3-2. longest = Math.max(longest, i - start + 1);
longest는 현재 2이고 Math.max(2, 2 - 0 + 1)로 3이 할당됩니다.

3-3. seen["h"] = i + 1;
seen["h"]의 value는 3이 할당됩니다.

4-1. let char = str[3]; // "o"

4-2. longest = Math.max(longest, i - start + 1);
longest는 현재 3이고 Math.max(3, 3 - 0 + 1)로 4가 할당됩니다.

4-3. seen["o"] = i + 1;
seen["o"]의 value는 4가 할당됩니다.

5-1. let char = str[4]; // "o"

5-2. if(seen["o"]) { start = Math.max(start, seen["o"]); }
seen이라는 객체에 이미 "o"이라는 키 값이 있기 때문에 뒤의 내용이 실행됩니다. Math.max(0, 4)로 4가 반환되며 start에 4가 할당됩니다.

5-3. longest = Math.max(longest, i - start + 1);
longest는 현재 4이고 Math.max(4, 4 - 4 + 1)로 4가 할당됩니다.

5-4. seen["o"] = i + 1;
seen["o"]의 value 값은 4에서 5로 바뀌어 할당됩니다.

6-1. let char = str[5]; // "l"

6-2. longest = Math.max(longest, i - start + 1);
longest는 현재 4이고 Math.max(4, 5 - 4 + 1)로 여전히 4가 할당됩니다.

6-3. seen["l"] = i + 1;
seen["l"]의 value는 6이 할당됩니다.

7. return longest;
for 반복문이 끝났으므로 longest의 현재값인 4가 출력됩니다.

위와 같이 처음부터 한 단계씩 문제를 파헤쳐보았습니다. 어떠한 방식으로 로직이 구현이 되는지 감은 잡히지만, 아직까지 100%를 이해했다고 보기엔 무리가 있습니다. 솔직히, 똑같은 문제로 혼자 문제를 풀이해보라고 하면 못풀 것 같습니다.

해당 문제는 포기가 아닌 유보를 시킨 상태로 진도를 나가야할 듯 싶습니다. 혹시 이해시켜주실 수 있는 분이 있다면 댓글 주시면 감사하겠습니다!😍

다음 시간에는 재귀 함수에 대해 알아보도록 하겠습니다.