[알고리즘 위한 한발짝 두발짝🐾] 투 포인터 기법

<본 블로그는 코딩문 codingmoon 님의 유튜브를 참고해서 공부하며 작성하였습니다 :-)>

=> 코딩테스트 필수 테크닉, 투 포인터 기법

 

🫧 투 포인터 테크닉

: 1차원 배열에서 각자 다른 원소를 가리키는 2개의 포인터를 사용하여 목표값 구한다

: 완전 탐색 O(n) 솔루션 -> O(n) 으로 성능 향상 가능

: 연속된 구간의 원소들을 처리하기 원하거나, 정렬된 배열에서 무언가를 구할 때 투포인터 사용

 

🐾 배열에서, 원소들의 합이 x인 연속 부분 배열의 개수를 구하라

arr = [1, 3, 6, 5, 2, 7, 9], x = 9

result : {3, 6}, {2, 7}, {9}

// 완전 탐색 O(n^2)
function cntSubArrSumOfX(arr, x) {
	let cnt = 0;
    for (let i = 0; i < arr.length; i ++) {
    	let sum = 0;
        for (let j = 0; j < arr.length; j++) {
        	sum += arr[j];
            if (sum > x) {
            	break;
            } else if (sum == x) {
            	cnt ++;
                break;
            }
        }
    }
    return cnt;
}

// 투 포인터 
function cntSubArrSumOfX(arr, x) {
	let cnt = 0;
    let sum = 0;
    let left = 0;
    let right = 0;
    
    while (right <= arr.length) {
    	if (sum === x) {
        	cnt ++
            sum -= arr[left]
            left ++
        } else if (sum < x) {
        	sum += arr[right]
            right ++
        } else if (sum > x) {
        	sum -= arr[left]
            left ++
        }
    }
    return cnt;
}

 

🐾 배열에서, 두 개의 원소의 합이 x 와 같은지 확인하고 그렇다면 각각 원소의 인덱스 반환하라

arr = [2, 4, 5, 7, 11, 15], x = 15

result : [1, 4]

// 완전 탐색 O(n^2)
function twoSumSorted(arr, x) {
	for (let i = 0; i < arr.legnth; i++) {
    	for (let j = 1; j < arr.length; j++) {
        	if (arr[i] * arr[j] === x && i != j) {
            	return [i, j]
            }
        }
    }
    return [-1, -1];
}

// 투 포인터 기법 
// 양 쪽에서의 sum 이 x 보다 크면 right --
// 양 쪽에서의 sum 이 x 보다 작으면 left ++

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