문제 해결 패턴 - Multiple Pointers

Multiple Pointers도  실제로 다중 포인터라고 불리지 않음. (공식 이름도 없음) 

 

 

이 패턴은 인덱스나 위치에 해당하는 포인터나 값을 만든 다음 특정 조건에 따라 중간지점에서부터 시작 지점이나 끝 지점이나 양쪽 지점을 향해 이동시키는 것이다.

 

문제 1. 합계가 0인 첫번째 쌍을 찾는 함수를 구현하자.

 

O(n^2) 으로 해결하는 방법

 

 

O(n)으로 해결하는 방법

(문제 1은 양쪽 지점에서 시작하여 반대편 지점으로 이동하면서 해결하는 방법을 사용하였다.)

 

// My Solution

validAnagram("", ""); // true
validAnagram("aaz", "zza"); // false
validAnagram("anagram", "nagaram"); // true
validAnagram("rat", "car"); // false) // false
validAnagram("awesome", "awesom"); // false
validAnagram("amanaplanacanalpanama", "acanalmanplanpamana"); // false
validAnagram("qwerty", "qeywrt"); // true
validAnagram("texttwisttime", "timetwisttext"); // true

function validAnagram(arr1, arr2) {
  if (arr1.length !== arr2.length) return false;

  const checkedArr1 = {};
  const checkedArr2 = {};
  for (const data of arr1) {
    checkedArr1[data] = (checkedArr1[data] || 0) + 1;
  }
  for (const data of arr2) {
    checkedArr2[data] = (checkedArr2[data] || 0) + 1;
  }

  for (const data in checkedArr1) {
    if (!checkedArr2[data] || checkedArr1[data] !== checkedArr2[data]) return false;
  }
  return true;
}

 

 

문제2. 고유값을 찾는 함수를 구현하자.

 

// My Solution
function countUniqueValues(arr) {
  if (arr.length === 0) return 0;
  if (arr.length === 1) return arr[0];

  let startIdx = 1;
  let tracerIdx = 0;
  while (startIdx < arr.length) {
    if (arr[startIdx] !== arr[tracerIdx]) {
      arr[tracerIdx + 1] = arr[startIdx];
      tracerIdx++;
    }
    startIdx++;
  }
  return tracerIdx + 1;
}

// Colt's Solution
function countUniqueValues(arr) {
  if (arr.length === 0) return 0;
  if (arr.length === 1) return arr[0];

  let i = 1;
  for (let j = 1; j < arr.length; j++) {
    if (arr[j] !== arr[i]) {
      i++;
      arr[i] = arr[j];
    }
  }
  return i + 1;
}


countUniqueValues([1, 2, 3, 4, 4, 4, 7, 7, 12, 12, 13]); // 7
countUniqueValues([1, 1, 1, 1, 1, 2]); // 2
countUniqueValues([]); // 0
countUniqueValues([-2, -1, -1, 0, 1]); // 4

 

 

 

 

 

본 내용은 작성자가 (Udemy) JavaScript 알고리즘 & 자료구조 마스터클래스 강의를 듣고 정리 및 메모한 내용입니다.  오역 및 오개념이 있을 수 있으니 바로잡기 위해 문제가 있는 경우 댓글 남겨주시면 매우 감사하겠습니다.

https://www.udemy.com/course/best-javascript-data-structures/

JavaScript (JS) Algorithms and Data Structures Masterclass