[알고리즘] javascript 문제해결 패턴 - Multiple Pointers (다중 포인터)

📌 Multiple Pointers (다중 포인터)

배열 속의 값을 비교해서 답을 도출할 때 사용 (주로 쌍으로 비교)
 

예시

1. 양쪽 끝에 포인터 배치

   오름차순으로 정렬된 배열 요소 중, 합치면 0이 되는 두 요소를 찾아 배열로 반환

   ex) [-2,1,0,2] ⇒ return [-2, 2]

    

   • best

     양쪽 끝에서 출발하는 포인터 설정 후, 비교하고 포인터 변경하면서 값 찾기

       let left = 0; // 왼쪽에서 출발하는 인덱스
       let right = arr.length -1 // 오른쪽 출발 인덱스
     
       while(left < right) { // 둘이 만나기 전에 종료
           let sum = arr[left] + arr[right];
           if(sum === 0) return 반환값
           else (sum > 0) right --; // arr[right]이 더 크므로 이동
           else left ++; // 

   • worst

       for 배열 순회
           for 배열 순회 (i+1부터)
           arr[i] + arr[j] = 0 이면 두 값 배열 반환 

      

2. 나란히 출발하는 포인터 배치
   고유한 값의 갯수 구하기

   ex) [1,1,2,3,3,3,4,4] ⇒ [1,2,3,4] ⇒ return 4

    

   • 나란히 출발하는 포인터 2개 설정 → 두 값 비교해서 다르면 i의 다음 자리에 j 값 넣음 → j는 계속 전진, i는 달라야 전진

       if(!arr.length) return 0; // 비어있으면 0 반환
       // 포인터 2개 생성
       let i = 0;
       // j는 순회하면서 증가
       for(let j = 1; j < arr.length; j++) {
           if(arr[i] !== arr[j]) { // 같지 않으면
               arr[++i] = arr[j]; // i를 오른쪽으로 옮기고 거기에 arr[j]값 넣기
           }
       }
       return i+1; 
       // 최종 arr의 모양은 [1,2,3,4,3,3,4,4] 이런식으로 됨
       // i는 인덱스 3에 멈춰있음

      

문제풀이

1. 배열 array와 숫자 n이 주어질 때, 배열에 평균이 n인 숫자 쌍이 있는지 확인하는 함수를 작성하시오.

   function averagePair(arr, n){
    if(arr.length < 2) return false;
   
    let left = 0;
    let right = arr.length-1;
   
    while(left < right) {
        let sum = arr[right]+arr[left];
        if(sum === n * 2) return true;
        if(arr[right]+arr[left] < 2*n) left++;
        else right--;
    }
    return false;
   }

    

2. 문자열 a, b가 주어질 때, a가 b에 순서대로 속해있는지 확인하는 함수를 작성하시오.

   function isSubsequence(str1, str2) {
    var i = 0; // str1의 비교할 index
    var j = 0; // str2의 비교할 index
    if (!str1) return true; // str1이 빈 문자열이라면 true 반환
    while (j < str2.length) { 
      if (str2[j] === str1[i]) i++; // 일치한다면 str1의 다음 인덱스로 넘어감
      if (i === str1.length) return true; // 끝까지 갔다면 true
      j++; // str2의 다음 인덱스로 넘어감
    }
    return false;
   }

    

---

참고

유데미 JavaScript 알고리즘 & 자료구조 마스터클래스