SLIDING WINDOW
Udemy - 【한글자막】 JavaScript 알고리즘 & 자료구조 마스터클래스
SLIDING WINDOW 기준점 간 이동 배열 패턴
This pattern involves creating a window which can either be an array or number from one position to another.
Depending on a certain condition, the window either increases or closes (and a new window is created).
Very useful for keeping track of a subset of data in an array/string etc. 배열/ 문자열 등에서 데이터의 하위 집합을 추적하는 데 매우 유용합니다.
#1. SLIDING WINDOW - maxSubarraySum
Write a function called maxSubarraySum which accepts an array of integers and a number called n. The function should calculate the maximum sum of n consecutive elements in the array.
maxSubarraySum([1,2,5,2,8,1,5],2) // 10
maxSubarraySum([1,2,5,2,8,1,5],4) // 17
maxSubarraySum([4,2,1,6],1) // 6
maxSubarraySum([4,2,1,6,2],4) // 13
maxSubarraySum([],4) // nulllet max = -Infinity로 설정! 양수로만 작업하지 않는 한 0에서 시작하는 것은 전혀 도움이 되지 않습니다.
//Time Complexity - O(N^2)
function maxSubarraySum(arr, num) {
if ( num > arr.length){
return null;
}
var max = -Infinity;
for (let i = 0; i < arr.length - num + 1; i ++){
temp = 0;
for (let j = 0; j < num; j++){
temp += arr[i + j];
}
if (temp > max) {
max = temp;
}
}
return max;
}||
REFACTOR
V
//Time Complexity - O(N)
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 - num] + arr[i];
maxSum = Math.max(maxSum, tempSum);
}
return maxSum;
}#Prac 7. Sliding Window - maxSubarraySum
위와 동일
#Prac 8. Sliding Window - minSubArrayLen
Write a function called minSubArrayLen which accepts two parameters - an array of positive integers and a positive integer.
This function should return the minimal length of a contiguous subarray of which the sum is greater than or equal to the integer passed to the function. If there isn't one, return 0 instead.
num보다 크거나 같으려면 arr에서 최소 몇개의 연속된 값이 필요한지
Examples:
- 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
Time Complexity - O(n)
Space Complexity - O(1)
🅰️ (제출 답) ✅ (풀이 과정)
배열에서 가장 큰 값을 기준으로 비교해볼까, 배열끝까지 더해나가다가 다시 빼기를 하자 등 이러쿵 저러쿵 시도하다가 실패하고 시간 너무 잡아먹어서 중단. 아래 풀이에서 else if 와 같은 조건을 넣어야 했는데 잘 안됐.. start, end 두 포인트를 잡아야... Infinity loop 안 빠지게 break 조건 넣는 것도 중요...
🤼♀️ 다른 풀이 1 (강의 솔루션)
function minSubArrayLen(nums, sum) {
let total = 0;
let start = 0;
let end = 0;
let minLen = Infinity;
while (start < nums.length) {
// if current window doesn't add up to the given sum then
// move the window to right
if(total < sum && end < nums.length){
total += nums[end];
end++;
}
// if current window adds up to at least the sum given then
// we can shrink the window
else if(total >= sum){
minLen = Math.min(minLen, end-start);
total -= nums[start];
start++;
}
// current total less than required total but we reach the end, need this or else we'll be in an infinite loop
else {
break;
}
}
return minLen === Infinity ? 0 : minLen;
}문제를 해결하려면 인접한 하위 배열의 시작과 끝을 추적해야 합니다. 이를 위해 슬라이딩 윈도우 접근 방식을 사용할 수 있습니다. 배열의 시작 부분에 시작 포인터와 끝 포인터를 유지합니다. 그런 다음 하위 배열의 합이 주어진 정수보다 크거나 같을 때까지 끝 포인터를 오른쪽으로 이동합니다. 이 조건이 충족되면 하위 배열의 합이 주어진 정수보다 작아질 때까지 시작 포인터를 오른쪽으로 이동합니다. 전체 배열을 순회할 때까지 이 과정을 계속합니다. 각 단계에서 하위 배열의 길이가 현재 길이보다 작으면 길이를 업데이트합니다. 합이 주어진 정수보다 크거나 같은 연속된 하위 배열이 없는 경우 0을 반환합니다. (출처: phind.com)
minSubArrayLen([2,3,1,2,4,3], 7) // 2입력값은 위와 같고, While문 끝나기 전에 console.log(total, start, end, minLen); 넣으면 아래와 같다.
2 0 1 Infinity
5 0 2 Infinity
6 0 3 Infinity
8 0 4 Infinity
6 1 4 4
10 1 5 4
7 2 5 4
6 3 5 3
9 3 6 3
7 4 6 3
3 5 6 2
#Prac 9. Sliding Window - findLongestSubstring
Write a function called findLongestSubstring, which accepts a string and returns the length of the longest substring with all distinct characters. //고유문자가 다 들어가는 구역의 길이
- findLongestSubstring('') // 0
- findLongestSubstring('rithmschool') // 7
- findLongestSubstring('thisisawesome') // 6
- findLongestSubstring('thecatinthehat') // 7
- findLongestSubstring('bbbbbb') // 1
- findLongestSubstring('longestsubstring') // 8
- findLongestSubstring('thisishowwedoit') // 6
Time Complexity - O(n)
🅰️ (제출 답) ✅ (풀이 과정)
function findLongestSubstring(str) {
//중복되면 멈추고, 길이를 저장해 두고, 기존에 중복되었던 부분의 앞부분을 자르고, 새로 탐색-
//멈추는 일이 발생해서 길이를 저장하는 순간이 오면, 기존 저장 값과 비교해서 길이가 큰 값 반환 -
//끝까지 오면 끝.
if(!str.length) return 0;
let tempStr = {0: str[0]};
let maxStr = 0;
let comLen = 0;
for (let i = 0; i < str.length; i++){
if(!Object.values(tempStr).includes(str[i])) {
tempStr[i] = str[i]
// console.log(tempStr)
} else {
//쪼개
let startIdx = Object.values(tempStr).indexOf(str[i]); //쪼갤 지점
tempStr = Object.values(tempStr).slice(startIdx+1);
tempStr[i] = str[i]
}
comLen = Object.values(tempStr).length;
if(maxStr < comLen) {
maxStr = comLen;
}
}
return maxStr;
}
🤼♀️ 다른 풀이 1 (강의 솔루션)
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;
};;