[ 자바스크립트(JavaScript) ] section05 - 5 - 최대 매출

📍 section05 - 5 - 최대 매출

연속된 K일 동안의 최대 매출액을 구하는 slidingWindow 문제인데 여기서 문제인 건 slidingWindow을 처음 배운것이다. twoPointer를 배웠다면 범위를 많이 벗어나지 않아서 다행이었다. N의 범위는 100,000까지인데, 만약, 시간복잡도가 O(N^2)이었다면 시간초과 판정을 받았을 것이다. 되도록 O(nlogn)이내로 끊자.

 

이 문제의 핵심 요지는연속된 3일간인데, 나는 while문으로 투 포인터를 사용하면서 rt-lt+1===k을 지키는 선에서 최대매출을 계산했다. 그와 비슷하게 강사님은 for문으로 푸셨는데, 이전에 k번째까지의 합을 구해놓고, sum을 누적하면서 k번째 이전의 인덱스를 계속 빼줬다. 즉, 이전 단계+현재 단계에 중복되는 수는 연산에서 제외시키고 다음 sum에 누적될 새로운 값과 k번째 이전의 값만 연산에 포함시키는 것이다.

 

k번째 이전의 인덱스만 빼주는 이유는 이전 index와 현재 index는 중복되기 때문인데, 만약 bruteForce로 풀었다면 중복값을 고려하지 않기 때문에 이중 반복문을 사용했을 것이다. bruteForce로도 풀어봤고 slidingWindow로도 풀었다.

 

 

728x90

 

 

// bruteForce
let n = 10;
let k = 3;
let arr = [12, 15, 11, 20, 25, 10, 20, 19, 13, 15];

for (let i=0; i<n-k+1; i++){
    let max = 0;
    for (let j=i; j<i+k; j++){
        max += arr[j]
    }
    console.log(max)
}

 

let n = 10;
let k = 3;
let arr = [12, 15, 11, 20, 25, 10, 20, 19, 13, 15];

// sliding window1 나의 코드
function solution(n, k, arr) {
  let lt = rt = currentSum = 0;
  let max = Number.MIN_SAFE_INTEGER;

  while (rt < n) {
    currentSum += arr[rt];
    if (rt-lt+1 === k) {
      max = Math.max(max, currentSum);
      currentSum -= arr[lt++];
    }
    rt++;
  }
  return max;
}

// sliding window2 강의 코드
function solution(n, k, arr) {
  let lt = rt = currentSum = 0;
  let max = Number.MIN_SAFE_INTEGER;
  let answer;

 for (let i=0; i<k; i++) currentSum+=arr[i];
 answer = currentSum;

 for (let i=k; i<n; i++){
     currentSum+=(arr[i] - arr[i-k])
		 answer = Math.max(answer, currentSum);
 }
return answer;
}