Sliding Window - minSubArrayLen
서론
저번 글에서 문제가 두 개 있고 두 번째 문제가 가장 어려웠다고 적었는데... 다시 보니 문제가 세 개 였고 세번째 문제가 정말 어려웠다. minSubArrayLen을 구현하는건 상대적으로 쉽게 풀 수 있었다. 이전에 maxSubArrayLen을 구했던 것의 반대로 하면 되기 때문이다. 자세한건 본론에서 계속 이어가겠다.
본론
maxSubarrayLen을 구현했을 때와 가장 큰 차이점은 기본값을 어떻게 설정하느냐였다.
maxSubarrayLen을 그현할 때 기본값을 -Infinity로 설정했으나 이번에는 다음과 같이 양의 무한대를 기본값으로 설정했다.
var minLen = Infinity;수를 더한 뒤에 같거나 크다면 왼쪽으로 윈도우의 시작점을 옮겼다.
if(sumVal >= val){
sumVal -= arr[left];
minLen = Math.min(minLen, right - left + 1);
left++;반대로, 더한 값이 val보다 작다면 윈도우의 끝을 오른쪽으로 늘렸다.
right++;
sumVal += arr[right];이렇게 하면서 수를 조절하면서 더한 수가 val과 같거나 크다면 minLen을 비교하고 저장한다.
이런식으로 문제 풀이가 가능했던 것은 minSubArrayLen에서 인자로 받은 배열의 속성들이 모두 정렬되어있기 때문이다.
몇 번이고 강조하지만 sliding window는 정렬된 선형의 자료구조에서 사용이 가능하다.
마지막으로 답을 반환할때는 다음과 같이 삼항연산자를 이용했다.
return minLen !== Infinity ? minLen : 0; 같거나 큰 값이 나오지 않았을 경우를 대비해, 그 때는 0을 반환해야하기 때문이다.
해설에서도 같은 방식으로 접근해 문제를 풀이했기 때문에 따로 추가로 소개하지는 않을 예정이다.
참고
웹개발