서론
오늘은 Multiple Pointers Pattern에 대해 배운것을 정리해 보도록 하겠다. 다중 포인터 패턴은 배열, 문자열, 이중 연결 리스트 같은 선형의 자료구조에서 사용할 수 있는 패턴으로, 인덱스나 위치에 해당하는 포인터 값을 만든 다음 조건에 따라 이동시키면서 한쌍의 조건이 맞는 데이터를 찾아내는 것이다. 예시를 보면서 더 자세히 이야기 하도록 하자.
본론
정렬된 배열에서 합이 0이 되는 한쌍의 값을 찾으시오
’‘’
sumZero([-3, -2, -1, 0, 1, 2, 3]) //[-3, 3]
sumZero([1, 2, 3]) // 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)
공간복잡도 O(1)
이게 가장 간단하고 쉽게 생각해 낼 수 있는 해결책이다. 하지만 시간복잡도가 O(n^2)으로 효율이 좀 떨어진다. 순서대로 데이터 하나를 포인터로 잡고 나머지를 모두 비교하는 방법인데 지금은 짧은 배열이라 문제가 없지만, 큰 배열이라면 시간이 오래 걸릴 것이다.
리팩토링 솔루션
이것을 리팩토링한 솔루션은 다음과 같다.
function sumZero(arr){
let left = 0;
let right = arr.length - 1;
//가운데 숫자가 0이었을때를 대비
While(left<right){
//양쪽 끝응 비교
let sum = arr[left] + arr[right];
if(sum === 0){
return [arr[left], arr[right]];
//끝의 숫자가 처음의 숫자보다 클 때 > 한칸 앞으로
}else if(sum>0){
right—;
// 오른쪽 숫자가 왼쪽보다 작음 > 더이상 math하는 숫자가 없음 > 다음 숫자 비교
}else{
right++;
}
}
}
시간복잡도 O(n)
공간복잡도 O(1)
물론 이 답들은 정렬된 배열에서 유효하다는 것을 알아야 한다. 정렬되어있지 않은 값의 배열에서는 좀 더 고민을 해야만 한다.
참고
