알고리즘 & 자료구조 스터디 4주차[multiple Pointers]

April 25, 2023 🐰

🔑 일반적인 문제 해결 패턴을 습득하기 (Problem solving Patterns)

💪🏻 이 친구들은 알고리즘을 패턴화해 문제 해결에 도움을 줄 수 있는 착한 친구들이다!

벌써 두개했다!! ✌🏻

🧠 frequency Counter
🧠 Multiple Pointers
🧠 Sliding Window
🧠 Divide and Conquer
🧠 Dynamic Programming
🧠 Greedy Algorithms
🧠 Backtracking
🧠 Many More!!!

🔑 Multiple Pointers Pattern

• 이 패턴의 개념은 인덱스나 위치에 해당하는 포인터나 값을 만든 다음 특정 조건에 따라 중간 지점에서부터 시작 지점이나 끝 지점이나 양쪽 지점을 향해 이동시키는 것이다.
• 배열이나 문자열과 같은 일종의 선형 구조나 또는 나중에 살펴볼 패턴들 중에 익숙하지 않지만 이중연결리스트나 단일연결리스트를 만드는 것이다.
• 즉 한 쌍의 값이나 조건을 충족시키는 무언가를 찾아야 한다.
• 다중 포인터는 두가지 reference를 필요로 한다.

👩🏻‍🌾 An Example Multiple Pointer

- 정렬된 배열을 취하는 sumZero라는 함수를 작성해보자 sumZero function

👩🏻‍🌾 Basic O(N^2) + Space Complexity -O(1)

• basic solution 이다.
  2중 for문을 이용해 배열 내에 있는 두개의 값의 합이 0 이되는 것을 찾는 것이다.

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]];
      }
    }
  }
}
let result = sumZero([-3, -2, -1, 0, 1, 2, 3]); // [-3,3]
sumZero([-2, 0, 1, 3]); //undefined
sumZero([1, 2, 3]); // undefined
console.log(result);

👩🏻‍🌾 Refactor Version O(N) + Space Complexity - O(1)

• left와 right를 사용한다.

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++;
    }
  }
}

let result = sumZero([-3, -2, -1, 0, 1, 2]); // [-3,3]
sumZero([-2, 0, 1, 3]); //undefined
sumZero([1, 2, 3]); // undefined
console.log(result);

👩🏻‍🌾 Coding Exercise2 : countUniqueValues

😼 Create countUniqueValues fn!
two pointer를 사용해서 정렬된 배열을 수락하고 배열의 고유 값을 카운트하는 countUniqueValues라는 함수를 구현합니다. 
배열에 음수가 있을 수 있지만 항상 정렬됩니다.

Time Complexity - O(n)
Space Complexity - O(n)

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

👩🏻‍🌾 my solution

• 강의의 solution과 방법이 동일해 패스!

function countUniqueValues(array) {
  let cnt = 0;
  let i = 0;
  let j = 1;
  //array의 길이가 0이라면 Return
  if (array.length === 0) return 0;
  // 조건을 부여 : 배열의 길이보다 작을 때 동안 루프
  while (j < array.length)
    if (array[i] === array[j]) {
          // 같다면 j++값을 증가시킴
      j++;
    } else if (array[i] !== array[j]) {
      // 같다면 i++값을 증가시킴
      i++;
      // 증가시킨 index에 index[j] 값을 넣기
      array[i] = array[j];
    }
  return i + 1;
}

countUniqueValues([1, 1, 1, 1, 1, 2]); // 2
let result = countUniqueValues([1, 2, 3, 4, 4, 4, 7, 7, 12, 12, 13]); // 7
countUniqueValues([]); // 0
countUniqueValues([-2, -1, -1, 0, 1]); // 4
console.log(result);

👩🏻‍🌾 Coding Exercise5 : averagePair

averagePair라는 함수를 작성합니다. 
정렬된 정수 배열과 목표 평균을 지정할 경우 쌍의 평균이 목표 평균과 동일한 값 쌍이 배열에 있는지 확인합니다. 
평균 대상과 일치하는 쌍이 둘 이상 있을 수 있습니다.

Time: O(N)

Space: O(1)

averagePair([1,2,3],2.5) // true
averagePair([1,3,3,5,6,7,10,12,19],8) // true
averagePair([-1,0,3,4,5,6], 4.1) // false
averagePair([],4) // false

👩🏻‍🌾 my solution

• Time : O(N) + Space O(1)
• left + right를 응용한 버전이다.
• left와 right의 평균값을 구하고 avg와 비교하는 문제.
• 강의와 역시 비슷한 solution이라 강의 solution 생략

function averagePair(array, avg) {
  let left = array[0];
  let right = array[array.length - 1];

  while (left < right) {
    let result = (left + right) / 2;
    if (result === avg) return true;
    else if (result > avg) right--;
    else left++;
  }
  return false;
}

👩🏻‍🌾 Coding Exercise6 : averagePair

isSubsequence라는 함수를 작성합니다. 
이 함수는 두 개의 문자열을 사용하여 첫 번째 문자열의 문자가 두 번째 문자열의 연속을 형성하는지 확인합니다. 
즉, 첫 번째 문자열의 문자가 순서를 변경하지 않고 두 번째 문자열의 어딘가에 나타나는지 여부를 확인해야 합니다.

isSubsequence('hello', 'hello world'); // true
isSubsequence('sing', 'sting'); // true
isSubsequence('abc', 'abracadabra'); // true
isSubsequence('abc', 'acb'); // false (order matters)


Your solution MUST have AT LEAST the following complexities:
Time Complexity - O(N + M)
Space Complexity - O(1)

👩🏻‍🌾 my solution

• copy 배열을 만든다
• 기존 두 배열을 비교하고 같으면 copy에 원소를 하나씩 추가한다.
• 마지막에 기존 array와 copy를 비교하여 Return!
• 잘했다.

  function isSubsequence(array, result) {
  //복사 배열 넣기
  var copy = [];
  let i = 0;
  for (let j = 0; j < result.length; j++) {
    //같으면
    if (array[i] === result[j]) {
      //값을 copy에 추가
      copy += array[i];
      i++;
    }
  }
  return array === copy;
  }

👩🏻‍🌾 solution - repeat

function isSubsequence(str1, str2) {
  var i = 0;
  var j = 0;
  if (!str1) return true;
  while (j < str2.length) {
    if (str2[j] === str1[i]) i++;
    if (i === str1.length) return true;
    j++;
  }
  return false;
}

👩🏻‍🌾 solution - 재귀

• 재귀는 볼 때마다 신박하다.

function isSubsequence(str1, str2) {
  if(str1.length === 0) return true
  if(str2.length === 0) return false
  if(str2[0] === str1[0]) return isSubsequence(str1.slice(1), str2.slice(1))  
  return isSubsequence(str1, str2.slice(1))
}

🔑 Review

• 재밌다.
• 비교적 쉬워서 재밌었던거 같다.
• 포인터를 이용한다는 것이 매우 복잡할 거 같지만 결국 짝을 만들어 비교하는거 같다.
• ??? : 친구가 있다는 건 공동책임

💻 Source

• ✏️ Best JavaScript Data Structures & Algorithms Course by Udemy, last updated January 2022, accessed April 5, 2023 - https://www.udemy.com/
• ⌨️ reference gitHub - https://github.com/seunghyun0522/JavaScript-Algorizms-Data-Structure