[Udemy] Sliding window 관련 문제 풀이

지난 시간에 배운 sliding window 관련 문제 풀이를 하면서 개념을 더 탄탄하게 익혀보자.

문제 1. minSubArrayLen

양수 배열과 양수 두 매개변수를 받는 함수가 있다. 주어진 정수 인자보다 인접한 요소의 부분합이 크거나 같은 하위 배열의 최소 길이를 반환하라.

minSubArrayLen([2,3,1,2,4,3], 7) // 2 -> because [4,3] is the smallest subarray
minSubArrayLen([2,1,6,5,4], 9) // 2 -> because [5,4] is the smallest subarray
minSubArrayLen([3,1,7,11,2,9,8,21,62,33,19], 52) // 1 -> because [62] is greater than 52
minSubArrayLen([1,4,16,22,5,7,8,9,10],39) // 3
minSubArrayLen([1,4,16,22,5,7,8,9,10],55) // 5
minSubArrayLen([4, 3, 3, 8, 1, 2, 3], 11) // 2
minSubArrayLen([1,4,16,22,5,7,8,9,10],95) // 0

 

일반적인 접근

function minSubArrayLen(arr, n) {
    if (arr.some(num => num >= n)) return 1;
    
    let minSubLen = 2;

    while (minSubLen < arr.length) {
        let sum = 0;
        for (let i = 0; i < minSubLen; i++) {
            sum += arr[i]
        }
    
        let temp = sum;
        for (let i = minSubLen; i < arr.length; i++) {
            temp = temp - arr[i-minSubLen] + arr[i];
            sum = Math.max(sum, temp);
    
            if (sum >= n) return minSubLen;
        }

        minSubLen++;
    }
    
    return 0;
}

 

슬라이딩 윈도우를 사용하여 부분합의 최댓값을 구하는 문제는 아래와 같이 접근하였다.
        
        1. 처음에 주어진 정수로 부분합의 max값을 구한다.
        2. 부분합 길이를 이동하면서 부분합에 첫번째 요소를 빼고 마지막 요소를 더하여 나온 결과값을 구한다.
        3. 초기 max 값과 나온 결과값을 비교하여 더 큰 값을 정한다.

위 과정에서는 부분합의 길이를 주어줬고 해당 길이의 부분합의 최대값을 반환하는 문제이다.

하지만, minSubArrayLen 문제는 정수 배열과 정수가 주어진다.
정수 배열의 부분합이 주어진 정수보다 크거나 같을 때의 최소 부분합 배열의 길이를 반환하라. 그래서 아래와 같은 방법으로 접근했다.

        0. 부분한 길이가 1일 때는 예외처리한다.
        1. 부분합 최댓값 문제에서는 부분합 길이가 주어졌지만, 여기선 주어지지 않았으므로 선언해준다.
        2. 선언한 부분합 길이로 부분합을 구한다.
        3. 부분합 길이를 이동하면서 첫번째 요소를 빼고 마지막 요소를 더한 결과값을 구한다.

 

하지만 위 코드는 while 반복문 내부에 for 반복문이 중첩되어 있으므로 시간 복잡도가 O(n^2)이다. 이를 sliding window 방법으로 바꿔서 풀어보자.

 

Sliding Window 방법으로 접근

function minSubArrayLen(nums, sum) {
  let total = 0;
  let start = 0;
  let end = 0;
  let minLen = Infinity;
 
  while (start < nums.length) {
    if (total < sum && end < nums.length) {
      total += nums[end];
      end++;
    }
    else if (total >= sum){
      minLen = Math.min(minLen, end-start);
      total -= nums[start];
      start++;
    }
    else {
      break;
    }
  }
 
  return minLen === Infinity ? 0 : minLen;
}

 

우선 슬라이딩 윈도우의 부분합을 담을 total, 포인터(start, end), 부분합 최소길이(minLen)을 선언한다.

 

슬라이딩 윈도우 시작 인덱스가 정수 배열 길이를 넘기 전까지 반복할 것 이고,

슬라이딩 윈도우 합이 주어진 sum 보다 작으면 끝부분 인덱스를 이동시키고 크거나 같으면 앞부분 인덱스를 이동시켜서

그 때마다의 슬라이딩 윈도우 길이값을 비교하여 작은 값을 저장해둔다.

 

1. 만약 현재 슬라이딩 윈도우가 주어진 합계(sum)을 넘지 않으면, 즉 total < sum 이고 end < nums.length 만족하면...

 

    → total에 값을 더해주고 end를 이동시킨다.

 

2. 만약 total이 sum보다 크거나 같으면...

 

    → minLen에 현재 minLen값과 슬라이딩 윈도우의 길이 중 작은 값을 할당한다.

    → total에서 슬라이딩 윈도우의 첫번째 요소를 빼고 start를 이동시킨다.

 

3. 만약 end 가 배열 길이까지 도달하고 total 값이 sum보다 작으면 중단한다.

 

    → 왜냐하면 슬라이딩 윈도우 부분합이 주어진 sum 보다 작거나 end가 끝에 도달하기 전이면 end 포인터를 움직여 슬라이딩 윈도우 값을 늘려나갈 수 있는데, 조건에 부합하기 어려우므로 중단한다.

 

결론적으로 슬라이딩 윈도우의 부분합값이 주어진 정수보다 크거나 같은지 혹은 작은지에 따라 포인터를 이동시켜주면 된다.

포인터를 이동시켜주면서 슬라이딩 윈도우의 부분합 값을 수정하고 슬라이딩 윈도우 길이를 비교하는 로직을 추가해주면 된다.

 

문제 2. findLongestSubstring

문자열을 받아 모든 하위 문자열이 고유한 문자열로만 구성된 문자열의 최대 길이를 구하여라.

findLongestSubstring('') // 0
findLongestSubstring('rithmschool') // 7
findLongestSubstring('thisisawesome') // 6
findLongestSubstring('thecatinthehat') // 7
findLongestSubstring('bbbbbb') // 1
findLongestSubstring('longestsubstring') // 8
findLongestSubstring('thisishowwedoit') // 6

 

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]);
    }
    // index - beginning of substring + 1 (to include current in count)
    longest = Math.max(longest, i - start + 1);
    // store the index of the next char so as to not double count
    seen[char] = i + 1;
  }
  return longest;
}

 

우선 변수를 선언한다.

 

- longest: 중복이 없는 가장 긴 문자열의 길이

- seen: 문자가 몇번째 위치에 등장했는지 담는 객체

- start: 현재 하위 문자열의 시작점을 나타내는 인덱스

 

반복문의 시작은 문자열 전체를 순회한다.

 

현재 문자를 char 변수에 저장하고,

longest는 start에서 부터 현재 인덱스 사이의 길이와 기존 longest 중 큰 값으로 수정한다.

seen 객체에 char를 key로 등록하고 현재의 인덱스를 value로 할당한다.

 

만약 이미 seen 객체에 등록된 문자가 등장하면,

start 위치를 seen 객체에 등록된 인덱스와 비교하여 큰 값으로 수정한다.

 

 

반복문을 문자열 길이만큼만 순회하면서 O(n)의 시간복잡도로 해결하려면 어떻게 해야할 지 막막했는데, sliding window 패턴을 배우고 비슷한 문제를 풀어보니 어느정도 이해가 되는 것 같다.

 

하지만 아직 완벽히 이해하고 있는 것이 아니므로 시간 날 때마다 이 글을 다시 보면서 패턴을 숙달해야겠다.

 

참조

Udemy - Js 알고리즘 & 자료구조 강의