JavaScript/Algorithm

Frequency Counter - Multiple Pointers

code10 2023. 3. 17. 14:11

Udemy - 【한글자막】 JavaScript 알고리즘 & 자료구조 마스터클래스

#1. Frequency Counter - Multiple Pointers

Write a function called sumZero which accepts a sorted array of integers. The function should find the first pair where the sum is 0. Return an array that includes both values that sum to zero or undefined if a pair does not exist

//Time Complexity - O(N^2)
//Space Complexity - O(1)

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

||

REFACTOR

V

//Time Complexity - O(N)
//Space Complexity - O(1)

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

#Prac2. Frequency Counter / Multiple Pointers - countUniqueValues

Implement a function called countUniqueValues, which accepts a sorted array, and counts the unique values in the array. There can be negative numbers in the array, but it will always be sorted.

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

Time Complexity - O(n)

Space Complexity - O(n)

🅰️ (제출 답) 

function countUniqueValues(arr){
    if(!arr.length) return 0;
    
    let result = 0;
    for(let i = 1; i < arr.length; i++){
      if(arr[i-1] !== arr[i]){
         result++;
      }
    }
    return result + 1;
}

✅ (풀이 과정)

=> 빈 배열이면 0 반환

=> for문의 index를 1부터 시작해서 이전값과 비교하고, 같지 않으면 result에 +1 해간다.

=> 마지막에 +1 이 최종 개수. (처음 result = 1로 설정하고 마지막에 result만 반환해도 마찬가지)

 

🤼‍♀️  다른 풀이 1 (강의 솔루션)

function countUniqueValues(arr){
    if(arr.length === 0) 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;
}

=> 비슷한 듯 약간 다른데, 첫 번째 포인트(내 풀이에선 i-1, 여기선 i)가 값이 달라질 때만 이동하는 방식이다. 내 풀이에선 계속 같이 전진한다.

=> 이런 식이다. [1(i),1(j),2,2,3] => [1,1=>2(i),2(j),2,3] => [1,2(i),2,2(j),3] => [1,2,2=>3(i),2,3(j)]  : i=2 이므로 최종값은 3

#Prac4. Frequency Counter / Multiple Pointers - areThereDuplicates

Implement a function called, areThereDuplicates which accepts a variable number of arguments, and checks whether there are any duplicates among the arguments passed in.  You can solve this using the frequency counter pattern OR the multiple pointers pattern.

Examples:

  1. areThereDuplicates(1, 2, 3) // false
  2. areThereDuplicates(1, 2, 2) // true
  3. areThereDuplicates('a', 'b', 'c', 'a') // true

Restrictions:

Time - O(n)

Space - O(n)

Bonus:

Time - O(n log n)

Space - O(1)

🅰️ (제출 답) 

function areThereDuplicates() {
    if(arguments.length < 2) return false;
    let obj = [];
    for (let value in arguments){
        if(!obj.includes(arguments[value])){
            obj.push(arguments[value]);
        } else {
            return true;
        }
    }
    return false;
}

✅ (풀이 과정)

1. 값이 일정하지 않아서 arguments를 이용

2. 빈 배열에 하나씩 담는 방식으로.. 포함하고 있지 않으면 담고,  포함하면 중복이므로 true 반환

3. 배열이 아닌 객체에 담는 방식으로 풀면 ↓

function areThereDuplicates2() {
    if(arguments.length < 2) return false;
    let obj = {};
    for (let value in arguments){
        if(obj[arguments[value]] === undefined){
            obj[arguments[value]] = (obj[arguments[value]] || 0) + 1;
        } else {
            return true;
        }
    }
    return false;
}

 

🤼‍♀️  다른 풀이 1 (강의 솔루션)

    function areThereDuplicates() {
      let collection = {}
      for(let val in arguments){
        collection[arguments[val]] = (collection[arguments[val]] || 0) + 1;
      }
        console.log(collection);
      for(let key in collection){
        if(collection[key] > 1) return true;
      }
      return false;
    }

=> 객체에 입력값을 키로, 1을 value로 담는데, 이미 존재하는 키에는(중복) +1이 되니까, 이 중 1 이상인 value가 있으면 true반환

 

🤼‍♀️  다른 풀이 2

function areThereDuplicates2() {
  let sortedArgs = Array.prototype.slice.call(arguments).sort();
  for(let i = 0; i < sortedArgs.length - 1; i++){
    if(sortedArgs[i] === sortedArgs[i+1]) return true;
  }
  return false;
}

=>  phind.com에서 해당 코드를 시간 복잡도 O(nlogn)으로 하면 어떻게 고치면 되냐고 물어봄. 아래는 해설.

주어진 코드의 시간 복잡도를 O(nlogn)으로 변경하려면 입력 배열을 반복하기 전에 정렬하면 됩니다. 배열을 정렬하면 O(nlogn) 시간 복잡도가 걸리고, 정렬된 배열을 반복하면 O(n) 시간 복잡도가 걸립니다. 따라서 코드의 전체 시간 복잡도는 O(nlogn + n)이 되며, 이는 O(nlogn)으로 단순화됩니다.
수정된 코드에서는 먼저 Array.prototype.slice를 사용하여 인수 객체를 배열로 변환한 다음 내장된 정렬 메서드를 사용하여 배열을 정렬합니다. 배열을 정렬하는 데는 O(nlogn) 시간 복잡도가 소요됩니다. 그런 다음 정렬된 배열을 반복하고 인접한 요소가 동일한지 확인합니다. 동일한 요소를 찾으면 참을 반환하여 인자에 중복이 있음을 나타냅니다. 중복 요소를 찾지 못하면 거짓을 반환하여 중복이 없음을 나타냅니다. 정렬된 배열을 반복할 때의 시간 복잡도는 O(n)입니다. 따라서 코드의 전체 시간 복잡도는 O(nlogn)입니다.

 

=> let sortedArgs = Array.prototype.slice.call(arguments).sort();

이 부분은 let sortedArgs2 = [...arguments].sort(); 이렇게 바꿔써도 됨.

https://stackoverflow.com/questions/63540420/what-is-the-difference-between-array-prototype-slice-callarguments-vs-args

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Functions/arguments#arguments_is_an_array-like_object

#Prac5. Frequency Counter / Multiple Pointers - averagePair

Write a function called averagePair. Given a sorted array of integers and a target average, determine if there is a pair of values in the array where the average of the pair equals the target average. There may be more than one pair that matches the average target.

Bonus Constraints:

Time: O(N)

Space: O(1)

Sample Input:

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

🅰️ (제출 답) ✅ (풀이 과정)

function averagePair(arr, avg){
  if(arr.length === 0) return false; //빈 배열이면 false 반환
  //반복문을 중복으로 돌려서, 두 값을 더한 값이 avg*2와 같으면 true 반환 
  for(let i=0; i<arr.length -1; i++){
    for(let j=1; j<arr.length; j++){
      if(arr[i]+arr[j] === avg*2) return true;
    }
  }
  return false;
}

=> 시간복잡도가 O(n^2)으로 좋지 않고, 비교했던 걸 또 비교하고 있어 매우 비효율적이다.

function averagePair(arr, avg){
    if(arr.length === 0) return false;
    let i = 0;
    let j = 1;
    while(i < j && j < arr.length){ 
        if(arr[i] + arr[j] === avg*2) {
            return true;
        } else if(j< arr.length) {
            j++;
        }
        if(j === arr.length){
            i++;
            j=i+1;
        }
        // console.log(`i: ${i}, j: ${j}`)
        if(i === arr.length -1){
            return false;
        }
    }
}

=> 적어도 앞에서 비교했던 건 빼려고 했는데...

 

🤼‍♀️  다른 풀이 1 (강의 솔루션)

function averagePair(arr, num){
  let start = 0
  let end = arr.length-1;
  while(start < end){
    let avg = (arr[start]+arr[end]) / 2 
    if(avg === num) return true;
    else if(avg < num) start++
    else end--
  }
  return false;
}

=> 강의 솔루션에서는 배열의 앞과 뒤의 값을 비교해간다. 이미 정렬된 배열이기때문에, 계산 값(avg)가 목표 값(num)보다 작으면 배열 앞부분에서 다음 값으로 비교해주기. 

#Prac6. Frequency Counter / Multiple Pointers - isSubsequence

Write a function called isSubsequence which takes in two strings and checks whether the characters in the first string form a subsequence of the characters in the second string. In other words, the function should check whether the characters in the first string appear somewhere in the second string, without their order changing.

Examples:

  1. isSubsequence('hello', 'hello world'); // true
  2. isSubsequence('sing', 'sting'); // true
  3. isSubsequence('abc', 'abracadabra'); // true
  4. isSubsequence('abc', 'acb'); // false (order matters)

Your solution MUST have AT LEAST the following complexities:

Time Complexity - O(N + M)

Space Complexity - O(1)

🅰️ (제출 답) ✅ (풀이 과정)

function isSubsequence(str1, str2) {
    //두 번째 문자열이 첫 번째 문자열보다 길이가 작으면 false;
    //두 번째 문자열을 하나씩 체킹하며, 첫 번째 문자열에 해당하면 첫 번째 문자열을 지우고, 
    //pop이 더 효율적이니 뒤에서부터 비교?
    //loop 끝나고 첫 번째 문자열 길이가 0이면 true; 아니면 false;
    if(str1.length > str2.length) return false;
    let arr1 = str1.split("")
    let arr2 = str2.split("")
    for(let i=arr2.length; i >= 0; i--){
        if(arr2[i] === arr1[arr1.length-1]){
            arr1.pop();
            arr2.splice(i, 1);
        }
    }
    return !arr1.length ? true : false;
}

=> 공간복잡도가 O(1)이 아니어서 정답이라고 할 수는 없다... 배열로 저장하지 않고, str1, str2로만 활용하여 (replace 함수를 이용해서) 다시 짜봤지만 그 역시 공간복잡도는 O(N)이었다. 문자열의 크기에 의존했기 때문이었다.

더보기

function isSubsequence(str1, str2) {
    if(str1.length > str2.length) return false;
    for(let i=str2.length; i >= 0; i--){
        if(str2[i] === str1[str1.length-1]){
            str1 = str1.replace(str1[str1.length-1], "");
            str2 = str2.replace(str2[i], "");
        } else if(!str1.length) return true;
    }
    return !str1.length ? true : false;
}

 

🤼‍♀️  다른 풀이 1 (phind)

phind.com ...
코드의 공간 복잡도가 O(1)이 되도록 수정하려면 입력 문자열의 크기에 의존하지 않는 일정한 양의 추가 공간을 사용하도록 코드를 수정해야 합니다. 이를 위한 한 가지 방법은 단일 루프 변수를 사용하여 str2를 트래버스하고 단일 인덱스 변수를 사용하여 str1의 현재 위치를 추적하는 것입니다. 이 접근 방식은 루프 변수와 인덱스 변수를 저장하는 데 일정한 양의 추가 공간만 필요합니다.
function isSubsequence(str1, str2) {
    if(str1.length > str2.length) return false;
    let j = 0;
    for(let i=0; i<str2.length; i++){
        if(str2[i] === str1[j]){
            j++;
        }
        if(j === str1.length) return true;
    }
    return false;
}
이 수정된 코드에서는 단일 루프 변수 i를 사용하여 str2를 트래버스하고 단일 인덱스 변수 j를 사용하여 str1의 현재 위치를 추적합니다. 루프는 i가 str2의 끝에 도달하거나 j가 str1의 끝에 도달하면 종료됩니다. 루프의 각 반복 동안 str1[j]와 str2[i]의 현재 위치에 있는 문자를 비교합니다. 둘이 같으면 j를 증가시켜 str1의 다음 문자로 이동합니다. 그렇지 않으면 단순히 i를 증가시켜 str2의 다음 문자로 이동합니다. 루프가 끝날 때 j가 str1의 끝에 도달했는지 확인하며, 이는 str1이 str2의 후속임을 나타냅니다. 이 수정 코드는 입력 문자열의 크기에 관계없이 루프 변수와 인덱스 변수를 저장하는 데 일정한 양의 추가 공간만 사용하기 때문에 공간 복잡도가 O(1)입니다.

=> for문을 이용하면 위와 같았고, while문을 이용하면 아래와 같다.

 

🤼‍♀️  다른 풀이 2 (강의 솔루션 / 반복)

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

 

🤼‍♀️  다른 풀이 3(강의 솔루션 / O(1) 공간이 아닌 재귀)

    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))
    }

=> 문자열이 같으면 잘라서 재귀, 다르면 str2만 잘라서 재귀