정렬이 되어 있는 자료에서 두 포인터가 가리키는 값이 반환하는 값을 찾아내는 탐색 알고리즘. 타겟 값을 반환하는 한 쌍을 찾을 때까지 이진 검색을 순환적으로 반복 수행하며, 메모리와 시간 절약을 가져온다. 투포인터의 시간 복잡도는 O(N)이다.
🔎 투포인터 이해하기
1. Reverse Pointers
배열의 양 끝에서 시작하는 투포인터 기법
❓오름차순으로 정렬된 배열에서 두 수의 합이 타겟이 되는 값을 탐색해야 하는 상황일 때를 가정한다. 1. 포인터1(처음)과 포인터2(끝)를 정의한다 2. 포인터1과 포인터2의 합과 타겟 값을 비교한다 3-1. 포인터1과 포인터2의 합이 타겟값보다 작으면, 포인터1을 우측(+1)으로 옮긴다 3-2. 포인터1과 포인터2의 합이 타겟값보다 크면, 포인터2를 좌측(-1)으로 옮긴다 4. 타겟을 찾을 때 까지 위의 과정을 반복한다
2. Same Direction Pointers
같은 방향으로, 속도만 다르게 이동하는 투포인터
❓오름차순으로 정렬된 배열에서 중복값을 제거해야 하는 상황일 때를 가정한다. 1. 포인터1과 포인터2 모두첫번째 원소의 인덱스를 가리키도록 정의한다 2. 이 때 포인터1은 고유값을 가리킬 거고, 포인터2는 루프를 돌면서 포인터1이 가리키는 값과 중복되는 값인지를 체크한다 3. 포인터1과 포인터2의 값이 다르면, 포인터1을 우측으로 이동시킨다 4-1. 포인터1과 포인터2의 값이 같으면(중복이면) 포인터2를 다른 값이 나올 때 까지 우측으로 이동시킨다 4-2. 다른값이 나오면, 포인터1을 우측으로 한 칸 이동시키고(공간을 만들고) 포인터2가 가리키는 값과 바꿔치기한다 5. 배열을 끝까지 탐색할 때 까지 위의 과정을 반복한다
⏳ 시간 복잡도
O(1) O(log N) O(N) O(N log N) O(N^2) O(2^N) O(N!)
👩🏻💻 코드 구현(JavaScript)
💡 Reverse Pointers example
❓오름차순으로 정렬된 배열에서 두 수의 합이 타겟이 되는 값을 탐색해야 하는 상황일 때를 가정한다.
// A: 배열, N: array 길이, X: 타겟
function isPairSum(A, N, X)
{
var i = 0; // 포인터 1
var j = N - 1; // 포인터 2
while (i < j) {
if (A[i] + A[j] == X) // 합계가 X가 되는 쌍을 찾으면 true 반환
return true;
else if (A[i] + A[j] < X) // X가 현재 합계보다 클 경우, 높은 숫자로 옮겨가 탐색
i++;
else // X가 현재 합계보다 작을 경우, 작은 숫자로 옮겨가 탐색
j--;
}
return false; // 찾지 못하면 false 반환
}
// nums: 배열
var removeDuplicates = function (nums) {
// 배열의 길이가 1이거나 1보다 작으면 어짜피 중복값 없음
if (nums.length <= 1) {
return nums.length;
}
// 배열의 길이가 1보다 큰 경우
let left = 0; // pointer1
let right = 0; // pointer2
while (right < nums.length) {
// 다르면 pointer1을 옮겨서 공간을 만들고
// 해당 공간에다가 pointer2가 가리키는 고유한 값을 할당한다
if (nums[left] != nums[right]) {
left++;
nums[left] = nums[right];
}
// 같으면 pointer2를 오른쪽으로 옮기기
right++;
}
return left + 1; // 문제에서 고유값의 갯수를 return하라고 요구
};
