Multiple Pointers

해당 글은 Udemy "JavaScript 알고리즘 & 자료구조 마스터 클래스" 수업을 기반으로 작성한 내용입니다.

 

오늘 함께 알아볼 알고리즘 문제 패턴은 일명 multiple pointer 라 불리는 알고리즘 패턴입니다. 이는 공식적으로 존재하는 패턴의 이름이 아니며 두개 이상의 포인터를 사용하여 알고리즘을 풀어내는 패턴을 가리킵니다. 해당 포인터의 시작은 양끝단에서 시작하기도 하고 같이 앞에서부터 시작하기도 합니다.

 

해당 패턴에서 한 가지 생각해야하는 것은 인자로 들어오는 배열이 정렬이 되어 있어야한다는 것입니다.

해당 패턴을 사용하게 되면 O(n)의 시간복잡도를 갖습니다.

 

sumZero

해당 문제는 배열의 두 요소를 더했을때 총 합이 0이 되는 두 요소를 배열에 담아 반환하는 문제입니다.

먼저 중첩 반복문을 이용하여 문제를 풀어보겠습니다.

 

웬만하면(?) 중첩배열은 사용하지 않는것이 좋습니다! O(n제곱)의 시간복잡도를 나타내기 때문에 코딩테스트의 시간 제한을 통과하지 못합니다.

 

1. 중첩 반복문을 이용하여 배열 순회하며 비교한다.
2. 두 요소의 합이 0이라면 해당 요소를 반환한다.

//nested for loop
 
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]];
      }
    }
  }
}

 

 

다음으로 multiple pointer pattern을 이용한 접근법을 살펴보겠습니다.

 

해당 문제는 포인터를 양 끝단에 위치시키는것을 이용한 방법입니다.

1. 변수 left, right를 선언한다 left에는 0을 right에는 인자로 들어오는 배열의 길이 - 1 로 설정한다.(두 변수는 pointer의 역할을 한다)
2. while문을 이용하여 left와 right를 인덱스로 하는 배열요소의 합을 변수 sum에 담는다. while문의 조건을 left < right로 설정한 이유는 두 포인터가 같이지는 경우, 배열에 0이 있는 경우를 걸러내지 못하기 때문이다.(left, right 포인터가 동일하게 0을 가리킬 경우, 두 포인터가 가리키는 요소의 합은 0이기 때문이다) right가 left보다 작다는 얘기는 서로 교차되었다는 의미이므로 확인할 필요가 없어진다.
3. 만약 sum이 0 이라면 해당 left와 right를 인덱스로 하는 배열의 요소를 반환한다.(해당 문제는 배열의 두 요소의 합이 0이 되는 최초의 경우만 반환하면 되기때문에 해당 지점에서 return을 하면된다.)
4. 만약 sum이 0 이상이라면 오른쪽 포인터(right)를 왼쪽으로 한 칸 이동시킨다.
5. 3, 4번의 경우도 아니라면 두 요소의 합이 0보다 작다는 말이므로 더 이상 해당 left를 확인할 필요가 없기 때문에 왼쪽 포인터(left)를 오른쪽으로 한 칸 이동시킨다.

//multiple pointer pattern
 
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++;
    }
  }
}

 

 

countUniqueValues

해당 문제는 인자로 들어온 배열의 고유한 값의 개수를 반환하는 문제입니다. 역시 multiple pointer pattern을 적용하기 위해서는 배열을 정렬해야합니다(해당 문제에서는 인자로 정렬된 배열이 들어온다고 가정하겠습니다.)

 

처음 문제를 해결했을때 frequency counter pattern 을 이용하였습니다. 빈 객체 object에 값이 담겼다는 것은 해당 배열의 요소가 존재한다는 것이고 객체 object의 각 key의 value에 상관없이 key의 개수만 체크하면 고유한 값이 체크되는 것이므로 객체 object key 값의 length를 반환합니다.

 

//내가 푼 방법
 
function countUniqueValues(array){
  if (!array.length) return 0;
  
  let object = {};
  for (let i = 0; i < array.length; i++) {
    object[array[i]] ? object[array[i]] += 1 : object[array[i]] = 1;
  }
  
  return Object.keys(object).length
}

 

해당 문제를 mulitple pointer pattern을 이용하여 풀어보겠습니다.

해당 문제는 앞쪽에서 두 포인터를 시작시켰습니다.

 

1. 먼저 빈배열의 경우 0을 반환하도록 early return 해준다.
2. 변수 i 에 0을 담는다.
3. 반복문을 선언하여 i 와 j를 index로 하는 배열의 요소들이 같은지 비교한다.
4. 두 요소가 다를 경우 고유의 값이라는 말이므로 더 이상 비교할 필요 없이 다음 요소로 넘어가 또다른 고유한 값을 찾도록 한다.
5. 반복문이 끝나고 고유한 값이 앞쪽으로 배치되므로 포인터 i 의 값에 1을 더한 값이 배열의 고유한 값의 개수가 된다.

//포인터 i 와 j 가 가리키는 요소의 값이 같기때문에 포인터 j를 오른쪽으로 한 칸 이동시킨다
i
[1, 1, 2, 3, 3, 4, 5, 6, 6, 7];
    j
 
//포인터 i 와 j 가 가리키는 요소의 값이 다르기 때문에 포인터 i를 오른쪽으로 한 칸 이동시킨다
//반복문에 의해서 j는 자동으로 한 칸 옮겨간다
//포인터 i를 오른쪽으로 옮긴 후 해당 포인터 i가 가리키는 요소에 해당 포인터 j가 가리키는 요소를 할당한다
 i
[1, 1, 2, 3, 3, 4, 5, 6, 6, 7];
       j
 
//최종적으로 다음과 같은 모습이 된다
                   i
[1, 2, 3, 4, 5, 6, 7, 6, 6, 7];
                            j

 

//multiple pointer pattern
 
function countUniqueValues(arr) {
  if (!arr.length) 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;
}
 
//[1, 1, 2, 3, 3, 4, 5, 6, 6, 7];