투포인터 알고리즘

리스트에 순차적으로 접근해야할 때 두 개의 점 위치를 기록하면서 처리하는 알고리즘
1차원 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작하면서 원하는 값을 찾을 때 까지 탐색하는 알고리즘

 

[동작방식]

• 보통 left, right / start, end 등의 포인터 변수 생성
• 처음에는 start = end = 0이고 두 포인터 관계는 start <= end
• 현재 부분 합이 target과 같다면 카운트
• 현재 부분 합이 target보다 작다면 end++;
• 현재 부분 합이 target보다 크거나 같다면 start++;
• 모든 경우를 확인할 때 까지 3~5 과정 반복

[예시 : 프로그래머스 Lv.2 구명보트]

function solution(people, limit) {
    var answer = 0;
    people.sort((a,b)=> a-b);
    let left = 0;
    let right = people.length -1;
    while(left <= right){
        if(people[left] + people[right] <= limit) left++;
        right--;
        answer++;
    }
    return answer;
}

 

[예시 : 프로그래머스 Lv.2 연속된 부분 수열의 합]

 

1차 풀이 : 실패

function solution (sequence,k){
     let check = sequence.indexOf(k);
    
     if(check > -1) return [check,check];
    
     for(let i =0; i< sequence.length; i++){
        
         for(let j =i+1; j< sequence.length; j++){
             let sum = sequence.slice(i,j).reduce((prev,cur)=> prev+= cur);
             if(sum == k) return [i, j-1];
         }
     }
     
     return -1;
}

 

2차 풀이: 성공

function solution(sequence, k) {
    let [left,right] = [0,0];
    let sum = sequence[0];
    let ret = [0, sequence.length];
    
    while(left < sequence.length){
        if(sum < k && right < sequence.length){
            sum += sequence[++right];
        }else if(sum == k && right -left < ret[1] -ret[0]){
            ret = [left,right];
            sum += sequence[++right];
        }else sum -= sequence[left++];
    }
    
    return ret;
}