[알고리즘&자료구조] Frequency Counter Pattern, Multiple Pointers Pattern

문제 해결 패턴 중 Frequency Counter 패턴(빈도카운터)과 Multiple Pointers 패턴(다중포인터)을 공부하였다.

빈도카운터 정확한 공식적인 이름이 있는게 아니지만 문제 해결할때 많이 등장하고 Colt Steele은 이를 frequencty counter 라고 정의하여 사용하기 때문에 이렇게 외우기로 했다.

 

Frequency Counter Pattern, 빈도 카운터 패턴

빈도카운터패턴은 애너그램 anagram과 같은 문제나, 두 배열이나 문자 string값을 비교하여 배열의 값들이 다른 한쪽의 배열의 제곱인지 체크하는 등에서 사용하는데 자바스크립트 객체의 속성접근을 이용하여 있는지 확인후 없다면 +1 있다면 있는 값의 +1 해주는 식으로 만들고 비교할때 하나씩 지우는 방식이다. 말로하기엔 이해하기 힘들기 때문에 코드를 보면 어떤 패턴인지 알 수 있다. 

이때 시간복잡도는 O(N)이 되게만들 수 있는 것이다.

function validAnagram(string1, string2) {
  if (string1.length !== string2.length) {
    return false;
  }
  let frequencyCounter1 = {};
  let frequencyCounter2 = {};
  for (let val of string1) {
    frequencyCounter1[val] = (frequencyCounter1[val] || 0) + 1;
  }
  for (let val of string2) {
    frequencyCounter2[val] = (frequencyCounter2[val] || 0) + 1;
  }

  for (let val in frequencyCounter1) {
    if (!(val in frequencyCounter2)) {
      return false;
    }
    if (frequencyCounter2[val] !== frequencyCounter1[val]) {
      return false;
    }
  }
  return true;
}

 

Multiple Pointers Pattern, 다중 포인터 패턴

다중 포인터 패턴의 경우 한가지 예시로 배열의 값들중 서로 더했을때 0 이 되는 값이 있는지 찾을때 사용했다.

[-3,-2,-1,0,1,2,3], [-2,0,1,3], [1,2,3] 등의 배열에서 서로 더했을때 0이 되는게 있는지 찾을때 Multiple Pointers 패턴을 사용하는 것이다.

처음 start포인터 왼쪽끝 부터 end포인터 오른쪽 끝을 더하면서 0인지 아닌지에 따라 왼쪽, 오른쪽으로 이동하며 비교하는 것이다.

이때 시간복잡도는 O(N)이 되게만들 수 있는 것이다.

코드를 보면 더 이해하기 쉽다.

// 리팩토리 전 방법
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])

//리팩토리후 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++;
    }
  }
}

sumZero([-4,-3,-2,-1,0,1,2,5])