[Udemy] Two pointer(투 포인터) 패턴 파악하기
오늘은 투 포인터 패턴에 대해 알아보자.
투 포인터는 인덱스나 위치에 해당하는 포인터나 값을 만든 후 특정 조건에 따라 포인터를 이동시키는 패턴을 말한다.
주로 배열, 문자열, 연결 리스트와 같은 선형 자료구조에서 한 쌍의 값이나 조건을 충족시키는 무언가를 찾을 때 사용된다.
문제 1.
오름차순으로 정렬된 배열에서 두 요소의 합이 0이 되는 첫번째 쌍을 찾아 반환하라.
input: [-3, -2, -1, 0, 1, 2, 3]
output: [-3, 3]
input: [-2, 0, 1, 3]
output: undefined
input: [1, 2, 3]
output: undefined
일반적인 접근
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)이다.
투 포인터 접근
function sumZero(arr) {
// 1. 투 포인터를 생성
let head = 0
let tail = arr.length - 1
// 2. 시작 인덱스가 끝 인덱스에 도달하기전까지
while (head < tail) {
let sum = arr[head] + arr[tail];
// 3. 합계가 0인지 아닌지 조건에 따라 포인터 이동
if (sum === 0) {
return [arr[head], arr[tail]]
} else if (sum > 0) {
tail--
} else {
head++
}
}
}시작 인덱스와 끝 인덱스를 투 포인터로 생성한다.
시작 인덱스가 끝 인덱스에 도달하기 전까지 시작 인덱스 값과 끝 인덱스 값의 합이 0인지 아닌지 조건에 따라 포인터를 이동한다.
문제 2.
오름차순 정렬된 배열의 고유한 숫자의 갯수를 반환하는 함수를 구현하라.
input: [1, 1, 1, 1, 1, 2]
output: 2
input: [1,2,3,4,4,4,7,7,12,12,13]
output: 7
input: []
output: 0
input: [-2,-1,-1,0,1]
output: 4
투 포인터 접근
1. 주어진 배열 변화 없이 구하기
문제 1번과 달리 문제 2번은 투 포인터 시작점이 왼쪽에서 부터 시작하고 curr, next 포인터로 시작한다.
function countUniqueValues1(arr) {
// 길이가 0이면, 0 반환
if (arr.length === 0) {
return 0;
}
// 0. 고유값 생성
let result = 1;
// 1. 투 포인터 생성
let curr = 0;
let next = 1;
// 2. 현재 포인터가 배열 마지막 요소일 때 까지 반복
while (curr < arr.length - 1) {
const currVal = arr[curr];
const nextVal = arr[next];
// 3. 현재 값과 다음 값이 같으면 다음 포인터 이동
if (currVal === nextVal) {
next++
// 4. 두 값이 다르면 결과에 1더하고 현재 포인터 다음 포인터로 이동
} else {
result++
curr = next++
}
}
return result;
}현재 포인터와 다음 포인터 값을 비교하여 다르면 현재 결과값에 1을 더하고 현재 포인터를 다음 포인터로 이동시킨다.
2. 주어진 배열 변화시키면서 구하기
function countUniqueValues3(arr) {
if (arr.length === 0) {
return 0;
}
let i = 0;
for (let j = 1; j < arr.length; j++) {
if (arr[i] !== arr[j]) {
i++;
arr[i] = arr[j]
}
}
return i + 1;
}현재 포인터를 0으로 두고 다음 포인터는 1부터 시작해서 끝까지 순회한다.
현재 포인터 값과 다음 포인터 값이 다르면, 현재 포인터를 +1 이동시키고 현재 포인터 값을 다음 포인터 값으로 수정한다.
ex) [5,5,10,10,20]에서 i = 0, j = 2일 때, 5 !== 10 을 만족하므로 i 를 +1 해주고 i 위치의 값을 j 위치의 값으로 수정한다.
-> [5,10,10,10,20]
참조