다중 포인터 패턴의 핵심은 배열이 있고, 인덱스에 맞게 2개이상의 포인터를 지정하고 조건에 따라 그 포인터의 위치를 하나씩 옮겨가며 문제를 해결하는 방법이다
문제 1
정수로 구성되어 있고 정렬된 배열이 주어질 때 두 수의 합이 0인 첫 번째 쌍의 정수를 구해야 한다.
예시)
1
2
3
sumZero([-3, -2, -1, 0, 1, 2, 3]) // [-3, 3]
sumZero([-2, 0, 1, 3]) // undefined
sumZero([1, 2, 3]) // undefined
풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const sumZero = array => {
let left = 0;
let right = array.length - 1;
while (left < right) {
let sum = array[left] + array[right];
if (sum === 0) {
return [array[left], array[right]];
} else if (sum > 0) {
// 두 수의 합이 0보다 크면 우측의 포인터를 감소 시킨다
right -= 1;
} else {
// 두 수의 합이 0보다 작으면 좌측의 포인터를 증가 시킨다
left += 1;
}
}
};
문제 2
정수로 구성되어 있고 정렬된 배열이 주어질 때 해당 배열의 유니크한 값의 개수를 리턴해라
예시)
1
2
3
countUniqueValue([1, 1, 1, 1, 2]) // 2
countUniqueValue([1, 1, 2, 3, 4, 4, 4, 5]) // 5
countUniqueValue([]) // 0
나의 풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function countUniqueValues(arr) {
if (arr.length === 0) {
return;
}
if (arr.length === 1) {
return 1;
}
let left = 0;
let right = 1;
while (right < arr.length) {
if (arr[left] === arr[right]) {
right += 1;
continue;
}
if (arr[left] !== arr[right]) {
left += 1;
arr[left] = arr[right];
}
}
return left + 1;
}
더 간단한 풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
function countUniqueValues(arr) {
if (arr.length === 0) return 0;
let i = 0;
for (let j = 1; j < arr.length; j += 1) {
if (arr[i] !== arr[j]) {
i += 1;
arr[i] = arr[j];
}
}
return i + 1;
}