다중 포인터

문제

다중 포인터 - averagePair

averagePair라는 함수를 작성합니다. 정렬된 정수 배열과 목표 평균이 주어졌을 때, 배열에 쌍의 평균이 목표 평균과 같은 값의 쌍이 있는지 확인합니다. 목표 평균과 일치하는 쌍이 두 개 이상 있을 수 있습니다.

 

보너스 제약조건:

Time: O(N)

Space: O(1)

 

예시 인풋:

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

 

 

문제 이해하기

Q) 쌍의 평균이 목표 평균과 같은게 존재하는지 찾아내기

input) [number], number

output) boolean

 

 

풀이

// 기존 코드
function averagePair(numArr, target){
  // 빈 배열인 경우 false 리턴
  if (numArr.length === 0){
      return false
  }
  
  // 배열 최고 인덱스 - 1까지 순회
  for (let i = 0; i < numArr.length - 1; i++){
    // 나머지 요소들과 평균구하기
    for (let restElement of numArr.slice(i + 1)){
        // 다음 요소와 평균이 목표 평균과 같은지 비교
        const average = (numArr[i] + restElement) / 2
        // 같으면 true 리턴
        if (average === target) {
            return true
        }
    }
  }
    
  // false 리턴
  return false
}

 

시간 복잡도를 n 제곱에서 n 으로 ​줄이기 위해 리팩토링을 진행했습니다.

기존에는 배열의 요소 쌍들을 한 번씩 더해서 찾아냈다면, 리팩토링한 코드는 배열 양 끝에 포인터를 생성했습니다.

평균이 목표 평균보다 큰 지, 작은 지에 따라 양 끝에 있는 포인터가 조정되도록 수정했습니다.

// 리팩토링 코드
function averagePair(numArr, target){
  // 빈 배열인 경우 false 리턴
  if (numArr.length === 0){
      return false
  }
  
  // 시작과 끝 포인터 생성
  let startPointer = 0
  let endPointer = numArr.length - 1
  
  // 시작 포인터가 끝 포인터보다 커지면 종료하는 반복문
  while (startPointer < endPointer) {
    // 포인터들 평균 구하기
    const average = (numArr[startPointer] + numArr[endPointer]) / 2
    // 평균이 타겟과 일치하면 true 리턴
    if (average === target) {
        return true
    }
    // 평균이 타겟보다 크면, 끝 포인터 1 감소
    if (average > target) endPointer--
    // 평균이 타겟보다 작으면, 시작 포인터 1 증가
    else startPointer++
    
      
  }
  // false 리턴
  return false
}