[ 자바스크립트(JavaScript) ] section05 - 3 - 연속 부분수열1

📍 section05 - 3 - 연속 부분수열1

N개의 수가 있을 때, 연속 부분 수열의 합이 target과 동일한 경우가 몇 번있는지 찾는 문제다. 이전까지는 이와 비슷한 유형의 문제를 풀어본 경험이 없기 때문에 어려웠다. N<=100,000 일 때 최대 O(nlogn)의 시간 복잡도를 만족해야 시간 초과를 받지 않는다. 즉, bruteForce(O(N^2)) 대신 다른 방법을 사용해야 한다.

 

코드에서는 while + while문을 사용했는데, 반복문을 2개 사용하면 무조건 O(N^2))이 되는 게 아닌가요?라고 할 수도 있다. 결론적으로는 그렇지 않다. 이중 반복문을 사용하더라도 그 안에서 어떤 연산을 했느냐에 따라 시간복잡도가 달라질 수 있는데, 현재 코드에서는 안쪽 루프가 도는 총횟수를 다 합했을 때 꼭 O(N)이 되지 않는다. 왜냐하면 안쪽 루프의 조건을 보면 sum>=m 인데, 만약, 현재 조건이 sum<m이라면 안쪽 루프는 실행되지 않을 것이기 때문이다.

 

1. 투 포인터 변수인 lt=rt=0으로 초기화한다.
2. sum 변수에 arr[rt] 값을 더한다.
3. sum === target 이면, cnt++해준다.
4. 만약, sum>target이면, lt를 증가해서 sum<=target이 될 때까지 빼줘야 한다.
5. while문 안에서 lt를 빼줬을 때도 3번 과정을 거친다. (여기서 알아두어야 하는 점은 sum===target이어도 lt를 빼줘야 다음 rt를 증가시킬 수 있다.)

728x90

// 나의 코드
let n = 8;
let target = 6;
let arr = [1, 2, 1, 3, 1, 1, 1, 2];

console.log(solution(n, target, arr));

function solution(n, target, arr) {
  let lt = (rt = cnt = sum = 0);

  while (rt < n) {
    sum += arr[rt++];
    if (sum === m) cnt++;
    while (sum >= m) {
      sum -= arr[lt++];
      if (sum === m) cnt++;
    }
  }

  return cnt;
}

 

// 강의 코드
let n = 8;
let target = 6;
let arr = [1, 2, 1, 3, 1, 1, 1, 2];

console.log(solution(n, target, arr));

function solution(n, target, arr) {
  let lt = (cnt = sum = 0);

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