[문제풀이] Frequency Counter / Multiple Pointers / Sliding Window

function sameFrequency(a, b) {
  // good luck. Add any arguments you deem necessary.
  const dicA = {};
  for (const digit of a.toString()) {
    dicA[digit] = dicA[digit] + 1 || 1;
  }

  for (const digit of b.toString()) {
    if (isNaN(dicA[digit]) || dicA[digit] < 0) return false;
    dicA[digit] = dicA[digit] - 1;
    if (dicA[digit] < 0) {
      return false;
    }
  }
  return true;
}

 

// Udemy Solution 
function sameFrequency(num1, num2){
  let strNum1 = num1.toString();
  let strNum2 = num2.toString();
  if(strNum1.length !== strNum2.length) return false;
  
  let countNum1 = {};
  let countNum2 = {};
  
  for(let i = 0; i < strNum1.length; i++){
    countNum1[strNum1[i]] = (countNum1[strNum1[i]] || 0) + 1
  }
  
  for(let j = 0; j < strNum1.length; j++){
    countNum2[strNum2[j]] = (countNum2[strNum2[j]] || 0) + 1
  }
  
  for(let key in countNum1){
    if(countNum1[key] !== countNum2[key]) return false;
  }
 
  return true;
}

 

// Use FrequencyCount
function areThereDuplicates(...args) {
  const dic = {};
  for (const data of args) {
    dic[data] = dic[data] + 1 || 1;
    if (dic[data] === 2) return true;
  }
  return false;
}

 

 

// Udemy Solution - Frequncy

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

 

 

// Udemy Solution - Multiple Pointers

function areThereDuplicates(...args) {
  // Two pointers
  args.sort((a,b) => a > b);
  let start = 0;
  let next = 1;
  while(next < args.length){
    if(args[start] === args[next]){
        return true
    }
    start++
    next++
  }
  return false
}

// Udemy Solution - One Liner
function areThereDuplicates() {
  return new Set(arguments).size !== arguments.length;
}

 

 

// My Solution
function averagePair(arr, num) {
  if (!arr.length) {
    return false;
  }
  let startIdx = 0;
  let endIdx = arr.length - 1;
  while (startIdx < endIdx) {
    const aver = (arr[startIdx] + arr[endIdx]) / 2;
    if (aver > num) {
      endIdx--;
    } else if (aver < num) {
      startIdx++;
    } else {
      return true;
    }
  }
  return false;
}

 

 

// udemy solution
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;
}

 

function isSubsequence(str1, str2) {
  // good luck. Add any arguments you deem necessary.
  let str1Idx = 0;
  let str2Idx = 0;
  while (true) {
    if (!str1[str1Idx]) return true;
    if (!str2[str2Idx]) return false;
    if (str2[str2Idx] === str1[str1Idx]) str1Idx++;
    str2Idx++;
  }
}

 

// Udemy Solution - use while
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;
}

 

 

// udemy solution - use recursion
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))
}

 

 

// My Solution
function maxSubarraySum(arr, windowSize) {
  if (arr.length < windowSize) return null;

  let tempMax = 0;
  for (let num = 0; num < windowSize; num++) {
    tempMax += arr[num];
  }

  let max = 0;
  for (let idx = windowSize; idx < arr.length; idx++) {
    tempMax = tempMax + arr[idx] - arr[idx - windowSize];
    max = Math.max(tempMax, max);
  }
  // console.log(max);
  return max;
}

 

 

// Udemy Solution
function maxSubarraySum(arr, num){
    if (arr.length < num) return null;
 
    let total = 0;
    for (let i=0; i<num; i++){
       total += arr[i];
    }
    let currentTotal = total;
    for (let i = num; i < arr.length; i++) {
       currentTotal += arr[i] - arr[i-num];
       total = Math.max(total, currentTotal);
    }
    return total;
}

 

 

minSubArrayLen([2,3,1,2,4,3], 7) // 2 -> because [4,31 is the smallest subarray
minSubArrayLen([2,1,6,5,4l, 9) // 2 -> because [5,4] is the smallest subarray
minSubArrayLen([3,1,7,11,2,9,8,21,62,33,19], 52) // 1 -> because [62] is greater than 57
minSubArrayLen([1,4,16,22,5,7,8,9,10],39) // 3
minSubArrayLen([1,4,16,22,5,7,8,9,10],55) // 5
minSubArrayLen([4, 3, 3, 8, 1, 2, 3], 11) // 2
minSubArrayLen([1,4,16,22,5,7,8,9,10],95) // 0

function minSubArrayLen(arr, num) {
  let minCount = Infinity;

  let sum = 0;
  let endIdx = 0;
  let startIdx = 0;
  while (startIdx < arr.length) {
    if (sum < num && endIdx < arr.length) {
      sum += arr[endIdx];
      endIdx++;
    } else if (sum >= num) {
      minCount = Math.min(minCount, endIdx - startIdx);
      sum -= arr[startIdx];
      startIdx++;
    } else {
      break;
    }
  }
  return minCount !== Infinity ? minCount : 0;
}

 

 

// Udemy Solution

function minSubArrayLen(nums, sum) {
  let total = 0;
  let start = 0;
  let end = 0;
  let minLen = Infinity;
 
  while (start < nums.length) {
    // if current window doesn't add up to the given sum then 
		// move the window to right
    if(total < sum && end < nums.length){
      total += nums[end];
			end++;
    }
    // if current window adds up to at least the sum given then
		// we can shrink the window 
    else if(total >= sum){
      minLen = Math.min(minLen, end-start);
			total -= nums[start];
			start++;
    } 
    // current total less than required total but we reach the end, need this or else we'll be in an infinite loop 
    else {
      break;
    }
  }
 
  return minLen === Infinity ? 0 : minLen;
}

 

findLongestSubstring('') // 0
findLongestSubstring('rithmschool') // 7
findLongestSubstring('thisisawesome') // 6
findLongestSubstring('thecatinthehat') // 7
findLongestSubstring('bbbbbb') // 1
findLongestSubstring( 'longestsubstring') // 8
findLongestSubstring('thisishowwedoit') // 6

// 처음에 짠 복잡한 코드
function findLongestSubstring(str) {
  let maxLength = 0;
  let startIdx = 0;
  let endIdx = 0;
  let strMap = new Map();

  while (startIdx < str.length && endIdx < str.length) {
    if ((strMap.has(str[endIdx]) && strMap.get(str[endIdx]) >= startIdx) || strMap.get(str[endIdx]) > startIdx) {
      maxLength = Math.max(maxLength, endIdx - startIdx);
      startIdx = strMap.get(str[endIdx]) + 1;
    }
    strMap.set(str[endIdx], endIdx);
    endIdx++;
  }
  maxLength = Math.max(maxLength, endIdx - startIdx);

  return maxLength;
}

// 나중에 다시 짠 그나마 나은 코드
function findLongestSubstring(str) {
  let maxLength = 0;
  let dict = {};
  let startIdx = 0;

  for (let endIdx = 0; endIdx < str.length; endIdx++) {
    let char = str[endIdx];
    // 이전에 처리한적 있으면
    if (!isNaN(dict[char]) && dict[char] >= startIdx) {
      startIdx = dict[char] + 1;
    }
    maxLength = Math.max(endIdx - startIdx + 1, maxLength);
    dict[char] = endIdx;
  }

  return maxLength;
}

 

 

// Udemy Solution
function findLongestSubstring(str) {
  let longest = 0;
  let seen = {};
  let start = 0;
 
  for (let i = 0; i < str.length; i++) {
    let char = str[i];
    if (seen[char]) {
      start = Math.max(start, seen[char]);
    }
    // index - beginning of substring + 1 (to include current in count)
    longest = Math.max(longest, i - start + 1);
    // store the index of the next char so as to not double count
    seen[char] = i + 1;
  }
  return longest;
}

 

 

 

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

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

JavaScript (JS) Algorithms and Data Structures Masterclass