[알고리즘] javascript 문제해결 패턴 - Sliding Window (기준점 간 이동)

📌 Sliding Window (기준점 간 이동)

배열 속 연속한 값을 이용해서 답을 도출하는 문제
 

예시

배열 속 n만큼 연속한 숫자들의 합 중, 최대값 구하기

⇒ 맨 처음부터 n개의 연달은 숫자의 합을 구하고, 두 개의 포인터를 이동해가며 (i-n, i) 앞꺼는 빼고, 뒤는 더해주면서 합계 비교

if(arr.length < n) return null;

let maxSum = 맨 처음 연달은 n개의 값의 합
let tempSum = maxSum; // 비교할 임시값

for (let i = n; i < arr.length; i++) { // maxSum에 더한 수 바로 다음 값부터 순회
    tempSum = tempSum - arr[i-n] + arr[i];
    maxSum = Math.max(maxSum, tempSum);
}

return maxSum;

 

문제 풀이

1. 주어진 배열의 n개의 연속하는 값을 합한 최댓값을 구하는 함수를 작성하시오.

    

   function maxSubarraySum(arr,n){
   if(arr.length < n) return null;
   
   let sum = 0;
   for(let i = 0; i < n; i++) {
       sum += arr[i]
     }
   let tempSum = sum;
   
   for(let i = n; i < arr.length; i++) {
     tempSum += arr[i] - arr[i-n];
     sum = Math.max(tempSum, sum);
   }
   
   return sum;
   }

 

2. 요소의 합이 전달된 정수보다 크거나 같은 연속 하위 배열 의 최소 길이를 반환하는 함수를 작성하시오. 없다면 0 반환.
    

   1. 두 개의 포인터가 동시 출발
   2. nums[end]의 값을 더하고, end+1로 하위 배열 넓힘 -> if가 끝나면 하위 배열은 0 ~ end-1 까지고, total도 그렇게 계산됨
   3. 만약 total이 sum보다 작으면, 위와 같이 end를 넓혀가며 total에 더해줌
   4. 만약 total이 sum보다 크면, 하위 배열의 크기를 결과값에 저장하고 (원값과 비교 후, 최소값이 저장됨) start--를 해서 하위 배열의 맨 앞 값을 빼고 크기를 줄여줌
   5. 이를 반복. end는 항상 하위 배열보다 한 칸 더 크게 위치하기 때문에 start와 만날 일이 없음
   6. 만약 end가 nums.length보다 커지거나 이외의 상황 발생 시, break (안 써주면 무한 루프됨)
   7. 모든 요소를 더해도 sum보다 작을 수 있기 때문에 sum이 infinity 인지 검사 후, 그렇다면 0반환, 아니면 원값 반환
       

   function minSubArrayLen(nums, sum) {
   
     let start = 0; // 시작,끝 인덱스 동시 출발
     let end = 0;
     let total = 0;
     let leastLgth = Infinity; // 최소 길이 초기값 설정
   
     while (start < nums.length) { 
   
         if (total < sum && end < nums.length) {
             total += nums[end]; 
             end++; // 배열 크기 넓히기 (이때 end는 하위 배열의 맨뒤 인덱스+1이 됨)
         } else if (total >= sum) { 
             leastLgth = Math.min(leastLgth, end - start); // 크기 업데이트
             total -= nums[start]; 
             start++; // 크다면 배열 크기 줄이기
         }
         else break; // end > nums.length일 경우 
     }
     return leastLgth === Infinity ? 0 : leastLgth;
   }

    

3. 주어진 문자열 안에서 연속한 고유한 문자의 최대 길이를 구하는 함수를 작성하시오.

    

   function findLongestSubstring(str){
     let startIdx = 0; 
     let result = 0; 
     while(startIdx < str.length) { 
         let obj = {}; // 중복 검사할 객체 
         for(let i = startIdx; i <= str.length; i++) { 
             if(obj[str[i]] || i === str.length) { 
                 result = Math.max(result, i - startIdx); 
                 break; 
             } 
             obj[str[i]] = 1; 
         } 
         startIdx ++; 
     } 
     return result; 
   }

    

   ---

참고

유데미 JavaScript 알고리즘 & 자료구조 마스터클래스