[투포인터 알고리즘]연속 부분 수열(1)

문제

N개의 수로 이루어진 수열이 주어집니다.이 수열에서 연속부분수열의 합이 특정숫자 M이 되는 경우가 몇 번 있는지 구하는 프로그램을 작성하세요.만약 N=8, M=6이고 수열이 다음과 같다면

1 2 1 3 1 1 1 2

합이 6이 되는 연속부분수열은 {2,1,3},{1,3,1,1},{3,1,1,1}로 총 3가지 입니다.

 

문제풀이

해당 배열에서 연속부분수열의 합을 구하기 위해서는 두 개의 인덱스가 포인터로서 순회 및 참조해야 하기 때문에중첩 반복문을 사용하였다. 

 

첫 번째 인덱스를 이용한 순회는 연속부분수열에서의 첫 번째로 기준이 되는 요소를 참조해야 한다.이때 연속부분수열의 합을 구해야 하기 때문에 첫 번째 기준이 되는 요소는 최초의 합산이 끝나면 그 다음 인덱스 요소를 참조해야 한다.

 

두 번째 인덱스를 이용한 순회에서는 첫 번째 기준이 되는 요소에서부터 합이 6이 될 때까지 각 요소들을 참조 및 합산해야 한다.

첫 번째 기준이 되는 요소에서 연속부분수열의 합이 나오지 않는다면 기준이 되는 요소는 그 다음으로 넘어가게 되고 해당 인덱스

요소를 시작으로 연속부분수열의 합이 6이 나오는지 식별해야 한다.

 

이를 위해 이전 인덱스 요소(이전 기준 인덱스 요소)는 연산에서 제외하기 위해 초기값을 (i+1)-1 으로 할당하여 주었다.

(초기값을 i+1 으로 할 경우에 i=0일 경우 중첩 반복문 내에서 첫 번째 인덱스 요소를 참조하지 못하는 문제가 생긴다)

 

코드

function solution(arr) {
  let answer = 0;

  for(let i = 0; i < arr.length; i++) {
    let sum = 0;
    for(let j = (i+1)-1; j < arr.length; j++) {
      sum += arr[j];
      if(sum === 6) {
        answer++;
        break;
      }
      if(sum > 6) {
        break;
      }
    }
  }
  return answer;
}

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

 

문제풀이2

투포인터 역할을 할 lt와 rt를 이용하여 연속부분수열의 합을 구하고자 한다.lt와 rt가 각각 참조하고 있는 인덱스 요소 사이의 합산을 통해서 중첩 반복문을 사용하지 않고 구할 수 있다.

 

연속부분수열의 합 n의 값보다 작을 경우(n보다 작을 때까지)에는 포인터 lt는 다음 인덱스를 참조하지 않고 그대로 둔 채, 포인터 rt만을 다음 인덱스 요소를 참조하게끔 이동시켜 준다.반대로 연속부분수열의 합 n의 값보다 크거나 작을 경우에는 n보다 그 값이 작아질 때까지 포인터 rt는 그대로 둔 채, 포인터 lt만을 다음 인덱스 요소를 참조하게끔 이동시켜 준다.

 

이때 포인터 rt와 같은 경우는, 인덱스 요소 사이의 합산한 값에는 다음에 참조될 인덱스 요소까지 포함되어야 하기 때문에 포인터다음으로 이동한 후에 합산 연산을 한다.반대로 포인터 lt와 같은 경우는, 인덱스 요소 사이의 합산한 값에는 이전에 참조됬던 인덱스 요소는 배제되어야  하기 때문에 포인터가 다음으로 이동하기 전에 감산 연산을 한다.

 

포인터 lt를 이동시키든 rt를 이동시키든 간에, 포인터의 이동 후 n의 값이 6이 될 경우에는 answer를 증감시켜 준다.

 

코드

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

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

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

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

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

  return answer;
}

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