효율성(투포인터 알고리즘) - 연속 부분수열 1

문제

 

배열 1 2 1 3 1 1 1 2이 있다

연속 부분 수열의 합이 특정 숫자(6)인 경우가 몇 번 나오는지 함수로 만들어 보시오.

{2, 1, 3}, {1, 3, 1, 1}, {3, 1, 1, 1} 로 3가지 이다.

 

입력예제 1          입력예제2

1 2 1 3 1 1 1 2     1 1 1 2 4

출력예제 1          출력예제2

3                       1

 

 

풀이

lt와 rt를 크기 비교할 일이 없이 rt는 증가하면서 sum에 더하는 일을 하면 되고,

lt는 증가하면서 sum에서 빼는 일을 하면 된다.

sum이 음수로 갈 일을 없으니 상관없다.

이론 설명처럼 rt가 증가하고 lt가 따라가는 것처럼 코드를 짜려면 아래처럼 하는게 더 이해하기 좋은 코드 이다.

코드1

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

  for (let rt = 0; rt < arr.length; rt++) {
    sum += arr[rt];
    while (sum > m) sum -= arr[lt++];
    if (sum === m) answer++;
  }
  return answer;
}
console.log(solution(6, [1, 1, 1, 2, 4])); // 1
console.log(solution(6, [1, 2, 1, 3, 1, 1, 1, 2])); // 3
console.log(solution(2, [1, 1, 1])); // 2

코드2

//더 나은 방법
function solution(m, arr) {
  let answer = 0, l = sum = 0;
  
  for (let r = 0; r < arr.length; r++) {
   sum += arr[r];
    while (sum >= m) {
      if (sum === m) {
        answer++;
      }
      sum -= arr[l++];
    }
  }
  return answer;
}
console.log(solution(6, [1, 1, 1, 2, 4])); // 1
console.log(solution(6, [1, 2, 1, 3, 1, 1, 1, 2])); // 3
console.log(solution(2, [1, 1, 1])); // 2

}

//----------------------------------------------//

function solution(m, arr) {
  let answer = 0,
    l = 0,
    sum = 0;
  for (let r = 0; r < arr.length; r++) {
    sum += arr[r];
    if (sum === m) answer++;
    while (sum >= m) {
      sum -= arr[l++];
      if (sum === m) answer++;
    }
  }
  return answer;
}
console.log(solution(6, [1, 1, 1, 2, 4])); // 1

//----------------------------------------------//

function solution(m, arr){
  let answer = 0, lt = rt = 0;
  let sum = arr[lt];

  while (rt < arr.length) {
    if (sum === m) {
      answer++;
      sum -= arr[lt];
      lt++;
    } else if (sum < m) {
      rt++;
      sum += arr[rt];
    } else {
      sum -= arr[lt];
      lt++;
    }
  }
  return answer;
}
console.log(solution(6, [1, 1, 1, 2, 4])); // 1

 

 

출처

자바스크립트 알고리즘 문제풀이(코딩테스트 대비) - 인프런 | 강의