[알고리즘] Multiple pointers

💡find Sumzero

sumZero라는 함수는 오름차순으로 정렬된 배열을 인자로 받아 합이 0이 되는 첫번째 쌍을 담은 배열을 반환하는 함수이다. 0이 되는 쌍이 존재하지 않으면 -1을 반환한다.

//다중 포인터를 이용한 해결 
//left와 right라는 이름의 두 개의 포인터를 활용한다. 

function sumZero(arr){
  let left = 0;
  let right = arr.length - 1;
  
  //left가 right보다 작은 동안만 반복되는 이유는
  //left가 right과 같은 경우 : 자기자신을 빼서 0이 나옴 
  //left가 right보다 큰 경우 : 교차됨 
  while(left < right){
    let sum = arr[left] + arr[right];
    if(sum === 0){
      return [arr[left],arr[right]];
    }else if(sum > 0){
      right--
    }else{
      left++
    }
  }
  return -1;
}

💡countUniqueValues

countUniqueValues라는 함수는 오름차순으로 정렬된 배열을 전달인자로 받아서 배열 속의 고유한 숫자가 총 몇 개인지를 세는 함수이다. (고유한 숫자 = 중복되지 않는 숫자)

//다중 포인터를 사용하지 않은 내 풀이 

function countUniqueValues(array){
  const unique = [];
  for(let val of array){
      if(!unique.includes(val)){
          unique.push(val);
      }
  }
  return unique.length;
}

//다중 포인터를 사용한 풀이 

function countUniqueValues(array){
  if(array.length === 0 ) return 0;
  
 let i = 0; 
  for(let j=1;j<array.length;j++){
    if(array[i] !== array[j]){
      i++;
      array[i] = array[j];
    }
  }
  
  return i+1;
}

//이 방법은 원 배열을 바꾸지 못한다는 조건이 있으면 사용할 수 없다.

💡 insight

• 위와 같은 방법으로 문제를 풀면 배열에 루프를 한 번 적용한 것과 같이 O(n)의 시간 복잡도가 나온다. 중첩 루프를 이용하거나 해서 해결하는 것보다 효율적인 방법이 된다.