슬라이딩 윈도우 & Two Pointer Algo

---

최대 매출

1. 누적값을 합산하는 sum변수 생성
2. 반복문을 이용하여 k길이 만큼의 누적값 생성
3. answer에 누적값 할당
4. k인덱스(k길이만큼 생성한 배열의 다음값)부터 시작하는 반복문 생성
5. 슬라이딩의 rt값에서 lt값을 빼고 누적값에 할당하며 전진
6. answer에 크기비교를 통해 최대값 할당

function solution(nums, k) {
  let sum = 0;
  let answer = 0;
  for (let i = 0; i < k; i++) {
    sum += nums[i];
  }
  answer = sum;
  for (let j = k; j < nums.length; j++) {
    sum += nums[j] - nums[j - k];
    answer = Math.max(answer, sum);
  }
  return answer;
}

매출액의 종류

1. 중복되는 값을 카운팅할 obj Map객체 생성
2. 반복문을 돌며 obj에 k-1만큼 길이의 배열을 카운팅
3. 슬라이딩에 필요한 lt변수 생성
4. 미리 생성한 배열의 다음 인덱스부터 시작하는 반복문 생성
5. obj에 카운팅을 한번 추가하여 원하는 k길이만큼 중복값이 카운팅
6. answer에 obj의 길이(size)를 push
7. obj에 배열 앞의 값을 갖고 있다면(무조건 있음) 카운팅 -1
8. 위의 작업 후 배열 앞의 값을 한번더 체크해 0이면 삭제(delete) {size에 반영되기때문}
9. lt++

function solution(nums, k) {
  let answer = [];
  let obj = new Map();
  for (let i = 0; i < k - 1; i++) {
    obj.set(nums[i], obj.get(nums[i]) + 1 || 1);
  }

  let lt = 0;

  for (let rt = k - 1; rt < nums.length; rt++) {
    obj.set(nums[rt], obj.get(nums[rt]) + 1 || 1);
    answer.push(obj.size);
    obj.set(nums[lt], obj.get(nums[lt]) - 1);
    if (obj.get(nums[lt]) === 0) obj.delete(nums[lt]);
    lt++;
  }
}

연속 부분수열1

음수가 포함될 시 슬라이딩 기법은 많이 다르게 변형됨

1. 슬라이딩에 필요한 lt생성
2. 누적값을 할당할 sum 생성
3. 반복문을 돌며 누적값 할당
4. 누적값이 m과 같아지면 answer++
5. 누적값이 m보다 클 경우 누적값에서 lt인덱스의 값들을 빼주며 lt++해주는 while구문 생성
6. while에서 누적값이 m과 같아지면 answer++
7. answer 반환

function solution(nums, m) {
  let answer = 0;
  let lt = 0;
  let sum = 0;

  for (let rt = 0; rt < nums.length; rt++) {
    sum += nums[rt];
    if (sum === m) answer++;
    while (sum > m) {
      sum -= nums[lt++];
      if (sum === m) answer++;
    }
  }
  return answer;
}

연속 부분수열2

강사님은 천재...

1. 누적값을 할당할 sum변수 생성
2. 특정값을 만났을 때 왼쪽의 누적값(경우의수)을 추가하기 위해 누적값을 카운팅하는 hash Map 생성
3. 반복문을 돌며 누적값 추가
4. 누적값 추가하는 중 m과 같으면 answer++
5. 만약 hash에 sum-m값이 있다면(반복문의 현재위치에서 누적값 중 카운팅된 경우의 수)
6. answer에 hash의 sum-m 키값의 카운팅값을 추가
7. hash에 현재 누적값 카운팅

function solution(nums, m) {
  let answer = 0;
  let sum = 0;
  let hash = new Map();
  for (let i = 0; i < nums.length; i++) {
    sum += nums[i];
    if (sum === m) answer++;
    if (hash.has(sum - m)) answer += hash.get(sum - m);
    hash.set(sum, hash.get(sum) + 1 || 1);
  }
  return answer;
}

연속 부분수열3

1. 누적값을 할당할 sum변수 생성
2. 슬라이딩을 위한 lt변수 생성
3. 반복문을 돌며 누적값 할당
4. 누적값이 m보다 클 때 누적값에서 lt인덱스 값을 빼며 lt++하는 while 반복문 생성
5. answer에 rt - lt + 1 추가 (누적값이 m보다 작은 모든 경우의 수 체크)
6. answer 반환

function solution(nums, m) {
  let answer = 0;
  let sum = 0;
  let lt = 0;

  for (let rt = 0; rt < nums.length; rt++) {
    sum += nums[rt];
    while (sum > m) {
      sum -= nums[lt++];
    }
    answer += rt - lt + 1;
  }
  return answer;
}

연속된 자연수의 합

1. 연속된 자연수의 반만 가면 되기 때문에 n의 반보다 1개 많은 길이의 배열 생성(index 순)
2. 누적값과 슬라이딩에 필요한 sum, lt 변수 생성
3. 반복문을 돌며 누적값 할당
4. 만약 누적값이 n과 같다면 answer++
5. n보다 커진다면 누적값에서 lt인덱스의 값을 빼고 lt++하는 while 반복문 생성
6. 만약 누적값과 n이 같다면 answer++
7. answer 반환

function solution(n) {
  let arr = Array.from({ length: parseInt(n / 2) + 1 }, (v, i) => i + 1);
  let sum = 0;
  let lt = 0;
  let answer = 0;

  for (let rt = 0; rt < arr.length; rt++) {
    sum += arr[rt];
    if (sum === n) answer++;
    while (sum > n) {
      sum -= arr[lt++];
      if (sum === n) answer++;
    }
  }
  return answer;
}

모든 아나그램 찾기

1. 새로운 Map객체 obj생성
2. obj에 t의 문자를 카운팅(음수로 카운팅)
3. 찾고자 하는 t만큼 반복문을 돌며 s에서 길이에 맞는 첫 아나그램 비교
4. 만약 s문자열에서 t문자열과 일치하는 키가 있다면 obj에서 일치하는 키를 삭제
5. 그렇지 않으면 새롭게 1카운트로 추가
6. t인덱스부터 시작하는 반복문 생성
7. 만약 s문자열에서 t문자열과 일치하고 그 값이 -1인 키가 있다면 obj에서 그 키를 삭제
8. 그렇지 않다면 새롭게 1카운트로 추가
9. 만약 obj의 크기(길이)가 0이라면 answer++
10. 만약 s문자열에서 t문자열과 일치하고 그 값이 1이라면 obj에서 그 키를 삭제
11. 그렇지 않다면 새롭게 -1카운트로 추가
12. lt++
13. answer 반환

function solution(s, t) {
  let obj = new Map();
  let lt = 0;
  let answer = 0;
  // Map 생성
  for (let x of t) {
    obj.set(x, obj.get(x) - 1 || -1);
  }
  // s에서 t만큼 돌면서 처음 아나그램 비교
  for (let i = 0; i < t.length - 1; i++) {
    if (obj.get(s[i]) === -1) obj.delete(s[i]);
    else obj.set(s[i], obj.get(s[i]) + 1 || 1);
  }
  for (let rt = t.length - 1; rt < s.length; rt++) {
    if (obj.get(s[rt]) === -1) obj.delete(s[rt]);
    else obj.set(s[rt], obj.get(s[rt]) + 1 || 1);
    if (obj.size === 0) answer++;
    if (obj.get(s[lt]) === 1) obj.delete(s[lt]);
    else obj.set(s[lt], obj.get(s[lt]) - 1 || -1);
    lt++;
  }
  return answer;
}

QUIZ: 사과따기

1. 슬라이딩에 필요한 lt, 부스트를 썼을 때 최대 사과값을 할당할 maxAp
2. 최대값에 맞는 부스트를 썼을때의 시작점 인덱스 idx 생성
3. 부스트 길이(m)만큼 반복문을 돌며 power가 0일때 maxAp에 누적값 추가
4. arr에 maxAp값 push
5. m인덱스부터 시작하는 반복문 생성
6. power 0일때 슬라이딩하며 maxAp에 누적값 할당
7. arr에 maxAp값 push
8. arr의 길이만큼 반복하는 반복문 생성
9. arr[idx]값보다 arr[j]가 더 크다면 idx에 j값 할당(부스트 시작위치 지정)
10. power에서 부스트 실행
11. 부스트를 실행한 power배열과 비교하며 answer에 최종 사과 누적값 할당
12. answer 반환

function solution(apples, power, m) {
  let answer = 0;
  let arr = [];
  let lt = 0;
  let maxAp = 0;
  let idx = 0;
  for (let i = 0; i < m; i++) {
    if (power[i] === 0) maxAp += apples[i];
  }
  arr.push(maxAp);
  for (let rt = m; rt < power.length; rt++) {
    if (power[lt] === 0) maxAp -= apples[lt];
    if (power[rt] === 0) maxAp += apples[rt];
    lt++;
    arr.push(maxAp);
  }
  for (let j = 1; j < arr.length; j++) {
    if (arr[idx] < arr[j]) {
      idx = j;
    }
  }
  while (m > 0) {
    power[idx++] = 1;
    m--;
  }
  for (let l = 0; l < apples.length; l++) {
    if (power[l] === 1) {
      answer += apples[l];
    }
  }
  return answer;
}