[JS] - 투포인트 알고리즘

투포인트 알고리즘

말 그대로 두 개의 포인터를 사용하는 알고리즘. 여기서 포인터는 C/C++의 포인터가 아니라, 어느 위치를 가르키는 개념적인 포인터다.

• 문제 조건이 연속/선행적으로 무언가를 해야할때 사용된다. 대부분이 아래 3가지 경우에 속한다.

Collision - One array, move from two sides to middle.
Forward - One array, both move forward.
Parallel - Two arrays, each array has been assigned with a pointer

• 슬라이딩 윈도우와 개념이 비슷하다

예제 연속부분수열

• 연속부분수열의 합이 특정숫자 M이 되는 경우가 몇 번인가.

1. arr[R]값을 sum에 더한다.

2. M(목표값)과 sum을 비교한다.

   2-1) 같은 경우, ans++

   2-2) sum이 M보다 작은 경우, R++

   2-3) sum이 M보다 큰 경우, sum -= arr[ L ], L++ 후 2.로 돌아간다.

3. 1.로 돌아가 반복한다.

• sum값이 목표값과 같을때에도 lt값을 증가 시켜주어야한다.~!

function answer2(){
            //연속하는 수 합 3
            let arr = [1,2,3,4,2,5,3,1,1,2];
            //let arr = [1,2,1,3,1,1,1,2];
            let n = arr.length;
            let lt = 0; 
            let find = 3;  // 6
            let sum = 0;
            let count =0; 
            for(let rt = 0;rt<n;rt++){
                sum += arr[rt];
                if (sum === find) count++;
                while(sum >= find){
                    sum -= arr[lt++];
                    if(sum === find) count++;
                }
            } 
            console.log(count);
        }

예제 연속부분수열2

• 연속부분수열의 합이 특정숫자 M보다 작은경우 몇 번인가.

function answer(){
            let N=5, M=5;
            let arr = [1,3,1,2,3];
            let memorize = Array.from({length:N} , ()=>[]); //추가공부
            let sum = 0;
            let lt = 0;
            let answer = 0;
            for(let rt=0;rt<N;rt++){
                sum += arr[rt];
                memorize[rt].push(arr[rt]);
                if(sum <= M) { 
                   //let value = [];
                //    for(let j=lt;j<=rt;j++){
                //        value.push(arr[j]);  
                //    }   
                    memorize[rt].push(value);
                    answer += rt-lt+1;
                }
                while(sum > M){
                    sum -= arr[lt++]; 
                    if(sum <= M) {
                        // let value = [];
                        // for(let j=lt;j<=rt;j++){
                        //     value.push(arr[j]);
                        // }   
                        // memorize[rt].push(value);
                        answer += rt-lt+1;
                    }
                }
            }       
            console.log(answer , memorize); 
        }