이번에 정리할 내용은 다중 포인터 패턴! 간단하게 설명하자면, 두개의 포인터가 고유값을 세는 것인데 아무튼 이에 대해서 코드와 함께 개념 정리를 해보자꾸!
🐣 정의
🌼 설명
이 패턴의 개념은 인덱스나 위치에 해당하는 포인터나 값을 만든 다음 특정 조건에 따라 중간 지점에서부터 시작 지점이나 끝 지점이나 양쪽 지점을 향해 이동시키는 것. 결론적으로 배열이나 문자열과 같은 일종의 선형 구조나 또는 나중에 살펴볼 패턴들 중에 익숙하지 않겠지만 이중 연결 리스트나 단일 연결 리스트를 만드는 것. 이런 패턴들 일단 몰라도 됨. 한 쌍의 값이나 조건을 충족시키는 무언가를 찾는다는 개념을 알아두기.
보통은 한 쌍을 찾음. 두 가지의 참조값을 사용. 참조값 하나는 여기서, 다른 하나는 여기서 시작하여 가운데로 서로를 향해 이동하도록 해주거나 참조값 하나는 여기서, 다른 하나는 여기서 시작할 수 있음. 참조값이란 인덱스를 가리키는 숫자인 i와 j 같은 변수를 의미. 따라서 i와 j를 여기에 입력하여 시작하여 특정 방향으로 이동하도록 하면 됨. 방향이 확실하지는 않음. 지난 영상에서 보았던 빈도 카운터 패턴과 비교하여 다소 느슨하게 정의되지만 그래도 자주 볼 수 있음.
요약부터 하자면, 여기에 포인터 변수는 배열이나 문자열의 특정 위치를 가리키는 것. 두 번째도 있으므로 서로를 향해 이동하거나 같은 방향으로 이동하든 끝에서부터 시작 위치로 이동하든 상관 없음. 다만 포인터를 두 개 사용하는 것.
🌼예시 sum_zero_naive.js (개선전)
Time Complexity : O(N^2)
Space Complexity : O(1)
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]];
}
}
}
}
sumZero([-4, -3, -2, -1, 0, 1, 2, 5])
분류(assorted)가 아니라 정렬(assorted)된 배열. 다만 오름차순. 이 함수는 합계가 0인 첫 번째 쌍, 즉, 한 숫자를 가져와 다른 숫자에 더하면 0이 되는 쌍을 찾음. 여기 -3이. 이 정렬된 배열에는 -3부터 +3까지 있습니다. 이 경우에 -3 더하기 +3은 0이므로 이 쌍은 배열로 반환. 그렇지 않으면 이 경우처럼 합이 0인 쌍이 없다면 undefined가 반환됨. 위에서 [-3,3]만 되어있는 이유는 합이 0이 되는 첫 번째 쌍을 찾아 반환하는 즉시 중지 됐기 때문.
문제 접근
배열이 정렬 되어 있어야 함
정렬된 배열의 경우 합계가 0이 되는 것을 찾으면 됨
설명
for문으로 배열 한번 돌리고, 그 안에서 for문으로 한번 더 배열 돌림 i+1로
각 배열 순회하면서 각 값 더해서 0이 되는 값 찾은 다음
return 값으로 해당 값 각각 반환
필요 없이 많은 작업 수행
특징
루프 2개 사용됨
모든 배열 순회하기 때문에 필요 없는 많은 작업 수행
🌼 예시 sum_zero_naive_refactored.js (리팩토링)
Time Complexity : O(N)
Space Complexity : O(1)
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++;
}
}
}
sumZero([-3, -2, -1, 0, 1, 2, 3])
설명
left와 right를 설정
while 반복문으로 left < right 될 때까지 진행
배열의 left 인덱스와 right 인덱스 값 더한 것을 sum
sum 이 0되면 arr[left]와 arr[right] 값 return
sum > 0 이면, right--;
위의 4-5 아닐경우(sum<0), left++;
🌼 예시 sum_zero_naive_refactored2.js
위의 경우 합계 0 되면 반환 후 종료. sum_zero_naive_refactored2의 경우 0 값에 해당하는 모든 값 출력하게 함.
function sumZeroAllPairs(arr) {
let left = 0;
let right = arr.length - 1;
const result = [];
while (left < right) {
let sum = arr[left] + arr[right];
if (sum === 0) {
result.push([arr[left], arr[right]]);
left++;
right--;
} else if (sum > 0) {
right--;
} else {
left++;
}
}
return result.length > 0 ? result : undefined;
}
console.log(sumZeroAllPairs([-3, -2, -1, 0, 1, 2, 3])); // [[-3, 3], [-2, 2], [-1, 1]]
설명
left, right 동일
result 배열 생성
while 반복문 sum === 0 일 경우 result에 arr[left]와 arr[right] 값 push 하고 left++, right--;
sum > 0 일 경우, sum < 0일 경우 처리 동일
최종 return값 result.length 확인 후, 0보다 크면 result 값 반환, 아니면 undefined 반환
두 번째 문제를 살펴보자. 다중 포인터나 투 포인터 패턴을 사용하여 해결 가능. 처음과 끝에서 가운데로 이동하는 게 아니라서 약간 다름. 그래도 마찬가지로 두 개의 포인터를 사용한다는 것이 관건. 조건에 따라 두 포인터가 특정 방향으로 움직이도록 하고 countUniqueValues라는 함수를 구현하여 앞서 작업과 마찬가지로 정렬된 배열을 전달하면 해당 배열의 고유한 값의 개수를 반환하도록. 음수가 포함될 수 있지만 항상 정렬된 상태로 있음. 이 경우에는 2를 반환. 고유한 숫자가 1과 2 두 가지만 있기 때문. 이 경우에는 7을 반환. 숫자값이 일곱 가지가 있기 때문. 고유한 숫자가 비어있는 한 고유한 값은 0. 여기에는 고유 값이 -2, -1, 0, 1 네 가지. 여기서도 투 포인터의 도움을 받을 수 있음. 이 해결책은 이전 해결책과 동일하지 않고 약간 다름. 다만 똑같이 두 개의 포인터를 사용.
문제 풀기 힌트
i, j(i+1) 배열 순회하면서, 같으면 j만 이동하고, 다르면 i 한칸 이동시키고 j에 있는 값 i 인덱스에 두기. 그렇게 계속 반복하고나면 i 인덱스까지의 배열이 고유 값들임. 결국 i+1이 고유값. 배열에 루프 1개 적용하여 O(n) 값일 것.
문제
다중 포인터 - countUniqueValues 정렬된 배열을 받아들이고 배열의 고유 값을 세는 countUniqueValues라는 함수를 구현합니다. 배열에 음수가 있을 수 있지만 항상 정렬.
(추가) 상수 또는 O(1) space 와 O(n) time으로만 이 작업을 수행해야 함.
🐣 solution
function countUniqueValues(arr) {
if (arr.length === 0) return 0;
var i = 0;
for (var j = 1; j < arr.length; j++) {
if (arr[i] !== arr[j]) {
i++;
arr[i] = arr[j]
}
}
return i + 1;
}
countUniqueValues([1, 2, 2, 5, 7, 7, 99])
설명
배열의 length 확인 후 0 이면 0 return
i에 0 값 넣기 (var)
for문을 돌리는데, j;
if문으로 arr[i]랑 arr[j]랑 다르면 i++ 해주고
arr[i] = arr[j] 같게 만들기(arr[j]를 arr[i]에 할당하여 i 위치를 이 새로운 고유 값으로 업데이트) > arr[i]값에다가 arr[j] 넣어서 새로운 값으로 !_!
i+1 값 return 하기 => 고유값 갯수!
과정 설명
초기 배열: [1, 2, 2, 5, 7, 7, 99]
i = 0, j = 1
arr[i]와 arr[j]를 비교
arr[0] = 1, arr[1] = 2
1 !== 2, 따라서 i를 증가시키고 arr[i]를 업데이트:
i++ -> i = 1
arr[1] = arr[1] -> 변경 없음, 배열은 [1, 2, 2, 5, 7, 7, 99]로 유지.
다음 반복:
j = 2
arr[1] = 2, arr[2] = 2
2 === 2, 따라서 i나 배열은 변경되지 않음.
다음 반복:
j = 3
arr[1] = 2, arr[3] = 5
2 !== 5, 따라서 i를 증가시키고 arr[i]를 업데이트
i++ -> i = 2
arr[2] = arr[3] -> 배열은 [1, 2, 5, 5, 7, 7, 99]가
다음 반복:
j = 4
arr[2] = 5, arr[4] = 7
5 !== 7, 따라서 i를 증가시키고 arr[i]를 업데이트:
i++ -> i = 3
arr[3] = arr[4] -> 배열은 [1, 2, 5, 7, 7, 7, 99]
다음 반복:
j = 5
arr[3] = 7, arr[5] = 7
7 === 7, 따라서 i나 배열은 변경되지 않음.
다음 반복:
j = 6
arr[3] = 7, arr[6] = 99
7 !== 99, 따라서 i를 증가시키고 arr[i]를 업데이트:
i++ -> i = 4
arr[4] = arr[6] -> 배열은 [1, 2, 5, 7, 99, 7, 99]
🤖 Quiz
문제
빈도수 세기 / 다중 포인터 - areThereDuplicates
가변적인 수의 인수(a variable number of arguments)를 받아들이고 전달된 인자 중 중복이 있는지 확인하는 areThereDuplicates라는 함수를 구현합니다. 빈도 카운터 패턴 또는 다중 포인터 패턴을 사용하여 이 문제를 해결할 수 있습니다.
예시:
areThereDuplicates(1, 2, 3) // false
areThereDuplicates(1, 2, 2) // true
areThereDuplicates('a', 'b', 'c', 'a') // true
제약 조건:
Time - O(n)
Space - O(n)
보너스:
Time - O(n log n)
Space - O(1)
정답1(빈도수세기)
function areThereDuplicates() {
let collection = {}
for (let val in arguments) {
collection[arguments[val]] = (collection[arguments[val]] || 0) + 1
}
for (let key in collection) {
if (collection[key] > 1) return true
}
return false;
}
정답2(다중포인터)
function areThereDuplicates(...args) {
args.sort((a, b) => a > b);
let start = 0;
let next = 1;
while (next < args.length) {
if (args[start] === args[next]) {
return true
}
start++
next++
}
return false
}
정답3(선형)
function areThereDuplicates() {
return new Set(arguments).size !== arguments.length;
}
