[27일차] Multiple Pointers

저요·2022년 10월 18일

2022 100th day challenge

목록 보기

27/97

문제

Multiple Pointers - averagePair

Write a function called averagePair. Given a sorted array of integers and a target average, determine if there is a pair of values in the array where the average of the pair equals the target average. There may be more than one pair that matches the average target.

Bonus Constraints
Time: O(N)
Space: O(1)
Sample Input
averagePair([1,2,3],2.5) // true
averagePair([1,3,3,5,6,7,10,12,19],8) // true
averagePair([-1,0,3,4,5,6], 4.1) // false
averagePair([],4) // false

해결책

본격적으로 들어가기 전에...

위 문제는 주어진 값과 같은 평균이 되는 숫자 한 쌍을 배열안에서 찾아내는 문제이다. 다중포인터 알고리즘을 사용하는 것이 조건인데 다중 포인터 알고리즘에 대한 더 자세한 이야기는 내 이전 게시글 들에서 확인 할 수 있다.

Multiple Pointers Pattern
https://velog.io/@eprnfmfmfm/16%EC%9D%BC%EC%B0%A8-Multiple-Pointers-Pattern
Multiple Pointers Pattern 2
https://velog.io/@eprnfmfmfm/20%EC%9D%BC%EC%B0%A8Multiple-Pointers-Pattern-2

averagePair 솔루션

function averagePair(arr, val){
  //변수생성
  var first = 0;
  var second = 1; 
  var valData = val*2;
  
  //첫번째 포인터와 두번째 포인터를 더해서 합계 구하기
  for(let i = 0; i<arr.length; i++){
      var sumData = arr[first] + arr[second];
      
      //합계가 평균*2와 같다면 true리턴
      if(sumData === valData){
          return true;
      }else if(sumData < valData){
          //합계가 평균*2 보다작다면 모두 한 칸씩 이동
          first++;
          second++;
      }else{
          //합계가 평균*2 보다 크다면 첫번째 포인터만 왼쪽으로 이동
          first--;
      }
  }
  
  return false;
}