[JavaScript/section 5] 04 - 연속 부분수열 2

📌 04 - 연속 부분수열 2(투 포인터 알고리즘)

N개의 수로 이루어진 수열이 주어진다. 이 수열에서 연속부분수열의 합이 특정 숫자 M이하가 되는 경우가 몇 번 있는지 출력하는 문제이다.

나의 풀이 방법

• for 문을 차례대로 돌며 포인터 rt의 위치를 이동시킨다.
• 포인터가 가리키고 있는 값을 sum에 누적시켜준다.
• sum이 m보다 작거나 같은 경우 answer++을 해준다.
• 포인터 rt가 가리키고 있는 값이 m 이하이고 sum과 같지 않다면 answer++을 해준다. 포인터 rt가 1씩 증가할 때마다 가리키고 있는 값이 특정 숫자 M이하가 되는 경우를 생각해야 하기 때문이다.
• 위 과정에서 sum이 m보다 크고 같아질 경우 포인터 lt가 가리키고 잇는 값을 sum에서 빼준다.
• sum이 m 이하이고 포인터 rt가 가리키고 있는 값과 같지 않다면 answer++을 해준다. 포인터 rt가 가리키고 있는 값과 같지 않아야 한다는 조건을 준 이유는 위에서 이미 해당 경우를 생각해 줬기 때문이다.
• for 문이 끝나면 answer을 return 해준다.

👍 강사님 풀이 방법

• for 문을 차례대로 돌며 포인터 rt의 위치를 이동시킨다.
• sum에 포인터 rt가 가리키고 있는 값을 sum에 누적시켜준다.
• 포인터 rt를 1씩 증가시킬때 마다 answer에 연속부분수열의 합이 특정 숫자 M이하가 되는 경우의 수(rt - lt + 1)를 더한다.
• 단, sum이 m보다 클 경우 포인터 lt가 가리키고 잇는 값을 sum에서 빼준다.
• for 문이 끝나면 answer을 return 해준다.

 

📝 풀이

// 나의 풀이 방법
function solution(m, arr) {
  let answer = 0,
    sum = 0,
    lt = 0;

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

  return answer;
}

let a = [1, 3, 1, 2, 3];
console.log(solution(5, a));

// 강사님 풀이 방법
function solution(m, arr) {
  let answer = 0,
    sum = 0,
    lt = 0;

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

  return answer;
}

let a = [1, 3, 1, 2, 3];
console.log(solution(5, a));