투 포인터(다중 포인터)

📌 투 포인터(다중 포인터)

이 전략의 기본 아이디어는 각각 배열의 인덱스에 해당하는 두 개 또는 여러 개의 포인터를 만들고, 제공된 조건에 따라 포인터를 배열의 시작, 끝, 중간으로 이동하여 한 쌍의 값 혹은 조건을 충족시키는 결과를 도출한다.

👀 Example 1

• 오름차순으로 정렬된 배열을 취하는 sumZero 함수를 만든다.
• 두 숫자를 더했을 때 0이 되는 쌍을 찾는다.

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

Solution

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), 공간 복잡도가 O(1)을 효율성이 떨어진다.

Refactored

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

오름차순으로 정렬되어 있다는 것은 왼쪽에 작은 수, 오른쪽에 큰 수가 있다는 의미가 된다. 이를 이용해 두 개의 포인터를 각각 가장 왼쪽, 가장 오른쪽에 두어 두 수의 합이 0보다 작으면 왼쪽 포인터를 앞으로 이동(+1)시키고, 두 수의 합이 0보다 크면 오른쪽 포인터를 뒤로 이동(-1)시키면서 두 수의 합이 0이 될때까지 반복한다. 이는 시간복잡도가 O(N), 공간복잡도가 O(1)으로 중첩 루프를 사용한 방식보다 훨씬 효율적이다.

 

👀 Example 2

• 정렬된 배열에서 주어진 숫자와 동일한 결합된 평균을 갖는 두 숫자를 찾는다.
• 예를 들어 주어진 배열이 [2,3,4]이고 주어진 숫자가 3.5인 경우 3과 4의 평균이 3.5이므로 3, 4가 결과값으로 도출되어야 한다.

const averagePair = (arr, num) => {
	let start = 0;
	let end = arr.length - 1;

	while(start < end) {
		let average = (arr[start] + arr[end]) / 2;
		if(average === num) {
			return `${arr[start]} and ${arr[end]} have an average of ${num}`
		} else if (average > num) {
			end--;
		} else {
			start++;
		}
	}
	return `None of these number pairs have an average of ${num}`
}

이 경우에도 배열의 시작과 끝 부분에 각각의 포인터를 두고, 조건을 충족하는 쌍을 찾을 때까지 반대쪽 끝으로 포인터를 이동시키면 된다. 'average' 변수의 값이 찾고 있는 숫자('num')보다 크면 두 번째 포인터('end')를 배열의 시작 부분에 더 가깝게 이동시킨다. 반대로 비교하는 숫자보다 작으면 왼쪽 포인터('start')를 앞으로 이동시킨다. 이 과정을 반복하여 원하는 결과값을 도출하면 된다.

 

https://levelup.gitconnected.com/using-the-multiple-pointers-strategy-to-solve-algorithms-b90a98f854db

Using the Multiple Pointers Strategy to Solve Algorithms