[알고리즘] 다중 포인터 패턴 (Multiple Pointers)

[알고리즘] 다중 포인터 패턴 (Multiple Pointers)

 

이 패턴은 인덱스나 위치를 나타내는 포인터나 값을 설정한 다음, 특정 조건에 따라 중간 지점에서 시작하거나 끝 지점을 향해 이동하는 것을 의미합니다.

결국, 배열이나 문자열 같은 선형 구조나, 이중 연결 리스트 또는 단일 연결 리스트 같은 구조를 다루는 방법입니다.

핵심은 한 쌍의 값이나 조건을 만족시키는 것을 찾는다는 개념입니다.

대부분의 경우, 한 쌍의 값을 찾게 됩니다.

 

 

문제

 

오름차순으로 정렬된 배열이 주어집니다.

이 배열에서 합계가 0인 첫 번째 쌍을 찾아야 합니다

즉, 배열에서 두 숫자를 찾아 그 합이 0이 되도록 하는 쌍을 찾는 함수입니다.

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

 

 

 

 

O(n^2)의 시간 복잡도 해결책

시간 복잡도 = O( n^2 )

공간 복잡도 = O(1)

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]];
            }
        }
    }
}

sumZero([-4,-3,-2,-1,0,1,2,5]); // [-2, 2]

 

 

 

 

 

O(n)의 시간 복잡도 해결책

시간 복잡도 = O( n )

공간 복잡도 = O(1)

function sumZero(arr) {
    let left = 0;
    let right = arr.length -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++;
        }
    }
}

 

 

 

 

 

참조!

https://www.udemy.com/course/best-javascript-data-structures/?couponCode=ST9MT71624