[코딩테스트] minSubArrayLen, 슬라이딩 윈도우 알고리즘

문제. 슬라이딩 알고리즘 - MinSubArrayLen

 

 

위 문제는 주어진 배열의 합이 숫자랑 같거나 큰 경우, 해당 배열합의 최소 길이를 반환하는 문제이다. 

즉, array와 sum이 주어지면 array 요소의 합이 sum보다 크거나 같은 최소 길이를 반환하면 된다.

이때 array 요소는 인접한 요소여야 한다. 

 

슬라이딩 윈도우 알고리즘을 통해 해결해야 하며, 시간복잡도는 O(n) 공간복잡도는 O(1)이여야 한다.

 

처음에 어떻게 풀어야 할지 감이 안왔다.

 

while문을 이용해서 한 칸씩 늘려가야 겠다는 생각을 하긴 했는데, 

어떻게 늘려가야 하지? 라는 고민이 계속 들었다. 

 

결국 시간이 지나도 문제를 맞추지 못해서 답안을 확인했다. 

 

*슬라이딩 윈도우 알고리즘 : 배열의 한 부분을 정의하고, 이 부분을 오른쪽으로 이동시키며 원하는 조건을 만족하는 것

 

답안.

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;
    }

    console.log(minSubArrayLen([2, 3, 1, 2, 4, 3], 7));

 

 

해당 문제는 주어진 배열에서, 합이 특정 값 이상이 되는 가장 짧은 길이의 연속된 부분 배열을 찾는 것이 목표이다. 

앞서 생각한대로 한 칸짜리 윈도우를 만든 후, 점차 윈도우를 크게 확대해 나가면서 해당하는 값을 찾아가면 된다.

 

 

let total = 0;
let start = 0;
let end = 0;
let minLen = Infinity;

 

우선 필요한 변수들을 정의해준다.

 

윈도우를 만들 때 필요한 start, end 변수와 윈도우 안에 있는 값들의 합을 넣을 total 변수를 만들어준다.

그리고 가장 작은 배열의 값을 넣을 minLen도 만들어준다.

 

minLen의 경우 다음에 어떤 값이 들어와도 값을 넣을 수 있도록 무한대로 설정해준다.

(뒤에 기존 배열과 새로운 배열의 길이를 비교해서 더 작은 숫자를 넣어야 하기 때문에)

 

 

while(start < nums.length){
	...
}

 

이제 while 문을 활용해 start 포인터가 nums(배열)의 끝까지 올때까지 반복문을 돌려준다.

 

우리는 total이 sum의 값보다 크거나 같아질때까지 end 변수를 통해 window를 한 칸씩 늘려나갈것이다.

start는 그 후에 이동하기 때문에 start 포인터가 nums.length와 같아진다면, 더 이상 확인할 배열이 없어진다.

 

따라서 while의 조건문을 start < nums.length로 설정해준다.

 

 

 

if(total < sum && end < nums.length){
    total += nums[end];
    end++;
}

 

total이 sum보다 작다면 window 크기를 늘려줘야 한다.

따라서 total에 end 포인터 값을 더해주고 end 포인터를 한칸 앞으로 당겨준다.

 

이때 end < nums.length 조건을 사용한 이유는 윈도우가 배열의 범위를 벗어나지 않도록 방지하기 위해서이다.

만일 end 포인터가 배열의 크기보다 커지면 안되기 때문에 반드시 조건을 달아줘야 한다. 

 

 

 

else if(total >= sum){
    minLen = Math.min(minLen, end-start);
    total -= nums[start];
    start++;
}

 

만일 total이 sum보다 크거나 같다면, minLen의 값을 이전 minLen과 현재 길이를 비교해 바꿔준다.

그리고 이보다 더 짧은 길이의 배열이 있을 수도 있기 때문에, start 포인터를 한 칸 앞으로 당겨준다.

 

 

else {
    break;
}

 

만일 total이 sum보다 작지만 end가 배열 끝에 도달했다면, 윈도우를 더 이상 확장할 수 없기 떄문에 반복문을 종료한다. 

 

 

return minLen === Infinity ? 0 : minLen;

 

마지막으로 minLen의 값이 Infinity라면 조건을 만족하는 연속된 요소가 없다는 의미이미로 0을,

그렇지 않다면 minLen을 반환해준다.