[알고리즘][JS] 다중 포인터 패턴

다중 포인터 패턴은 공식이름이 아닙니다.

다중 포인터 패턴

배열이나 리스트와 같은 데이터 구조에서 특정 조건을 만족하는 요소를 찾거나 조작하는데 사용되는 알고리즘 기법.

한쌍의 값이나 조건을 충족 시킨다는 개념만 알면 됨.

두가지의 참조값을 사용한다.

[1,2,3,4,5,6,7]
"asdfasdgaaxvasdFF"

두가지의 참조값을 설정하여 어느 한 곳으로 이동시키며 비교한다.

서로를 향하든 혹은 서로를 향하지 않고 한곳으로 이동하든.

예시

sumZero([-3,-2,-1,0,1,2,3]) // [-3,3]
sumZero([-2,0,1,3]) // undefined
sumZero([1,2,3]) // undefined

sumZero라는 함수는 정렬된 배열을 가진 함수입니다.

1번째 배열에서 -3 3을 더한다면 0이기 때문에 [-3,3]을 반환합니다

밑의 두개의 함수는 undefined를 반환합니다. ( 더했을 시, 0이 반환되는 값이 존재하지 않기 때문에 )

답안 (수정 전)

function sumZero(arr){
	for(let i = 0; i < arr.length; i++){
    	for(let j= i+1; j < arr.length; j++){
        	if(arr[i] + arr[j] === 0){
            	return [arr[i], arr[j]];
            }
        }
    }
}

// O(n^2)의 복잡한 시간복잡도

for 루프를 2번 도는 비효율적인 답안으로 보임.

-3을 찾는 포인터 시작 후 나머지 모든 값들을 비교함.

00 01 02 03 ~~ 이런식으로 모든 값을 비교하기 때문에 비효율 적임.

다중 포인터 패턴 답안 (수정 후)

  function sumZero(arr){
                let left = 0
                let right = arr.lengh - 1
                
                while(left < right){
                    let sum = arr[left] + arr[right]
                    if(sum === 0){
                        return [arr[left],arr[right]]
                    } else if(sum > 0){
                        right--
                    } else {
                        left++
                    }
                }
}

이 함수는 포인터 패턴을 이용하여 시간복잡도를 O(n^2)인 이전 함수에 대비해

O(n)인 선형리스트로 복잡도를 낮춘 함수입니다.

 

반복적으로 두개의 값을 더하지만 모든값을 비교하는 것이 아닌,

두개를 더했을때 양수라면 우측의 절댓값이 더 큰것이기 때문에 우측의 값을 하나 빼서

인덱스가 하나 내려오게하여 비교합니다.

 

음수라면 좌측의 절댓값이 더 큰 것 이기 때문에,

좌측의 인덱스를 나타내는 값이 하나 올라 오려면 left에 ++을 해줍니다.

 

이런식으로 비교를하다가 맞는값이 나오면 첫번째 if문에서 원하는 값을 return 해줍니다.

없다면 undefined를 반환합니다.