빈도수 세기 패턴

두 문자열을 입력 받아 순서 상관 없이 알파벳의 개수가 같을 경우 true 다를 경우 false를 return하는 함수.
이런 경우 이중 for문을 쓸 수 있지만 시간 복잡도 O(n)을 위해 아래처럼 for문을 2번 사용하여 해결할 수 있다.

function validAnagram(first, second) {
    // add whatever parameters you deem necessary - good luck!
    if (first.length !== second.length) return false; // 문자열의 길이가 다르면 false

    const lookup = {};

    for (let chr of first) {
        lookup[chr] ? lookup[chr] += 1 : lookup[chr] = 1;
    }

    for (let chr of second) {
        if (!lookup[chr]) return false; // 순회도중 second에 없는 문자열이 발견된 경우 false
        else lookup[chr] -= 1; // 객체에서 순회중인 알파벳의 빈도를 제거한다.
    }
    return true; // 위의 과정이 모두 완료되면 { a:0, b:0, c:0 }이 된 상황이고, 이는 조건에 충족하므로 true를 반환한다.
}


log(validAnagram('cabc', 'abcc')); // true

다중 포인터 패턴

배열 고유 값의 개수를 구할 때, filter method를 이용하거나, 아래처럼 다중 포인터를 활용할 수 있다. 그 밖에 sort된 데이터를 다룰 때 자주 활용된다.

function countUniqueValues1(arr) {
    // add whatever parameters you deem necessary - good luck!
    arr.sort();
    return arr.filter((v, i) => arr.indexOf(v) === i).length; // 중복제거
}

function countUniqueValues2(arr) {
    // add whatever parameters you deem necessary - good luck!
    let pointer1 = 0;
    arr.sort();
    for (let pointer2 = 1; pointer2 < arr.length; pointer2++) {
        if (arr[pointer1] !== arr[pointer2]) {
            pointer1++;
            arr[pointer1] = arr[pointer2];
        }
    }
    return pointer1 + 1
}
log(countUniqueValues1([1, 2, 2, 3, 1, 5, 6, 3])); // 5
log(countUniqueValues2([1, 2, 2, 3, 1, 5, 6, 3])); // 5


function areThereDuplicates(...args) { // 중복값 있을경우 true
  // 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
}

function averagePair(arr, num){ // 요소 중 2가지의 평균이 num인 것이 존재하면 true
  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) { // str1의 문자열이 str2에 포함되어 있으면 true (순서는 일정해야 함)
  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;
}

슬라이딩 윈도우 접근법

arr의 숫자를 num만큼의 범위씩 더하여 합계를 냈을 때, 가장 큰 영역을 구하는 함수다.
이 때, 이중 for문을 통해 모든 루프를 도는 방법도 있지만 아래처럼 O(n)의 시간복잡도를 위해 슬라이딩 윈도우 접근법을 통해 문제를 해결할 수 있다.

초기합계를 구한 뒤 모든 루프를 순회하는 것이 아니라 범위만큼 배열을 이동하면서 새로 편입되는 요소를 더해주고 나가게된 요소를 빼주는 식으로 동작하는 것이 슬라이딩 윈도우다.

function maxSubarraySum(arr, num){
  let maxSum = 0;
  let tempSum = 0;
  if (arr.length < num) return null;
  for (let i = 0; i < num; i++) {
    maxSum += arr[i];
  }
  tempSum = maxSum;
  for (let i = num; i < arr.length; i++) {
    tempSum = tempSum - arr[i - num] + arr[i];
    maxSum = Math.max(maxSum, tempSum);
  }
  return maxSum;
}

maxSubarraySum([2,6,9,2,1,8,5,6,3],3)


function minSubArrayLen(nums, sum) { // 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;
}


function findLongestSubstring(str) { // 문자열 내에서 중복되는 문자가 없다는 조건 하에 가장 큰 길이의 연속되는 substring
  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;
}

분할 정복 패턴 (이진탐색)

정렬된 상태의 데이터라면 이진 탐색을 사용할 수 있다. 배열 전체의 중앙에서 시작하여 추적하는 값의 범주를 반씩 줄여나가는 패턴으로서 이런 패턴은 O(logN)의 시간 복잡도를 가진다.

function search(array, val) {
  let min = 0;
  let max = array.length - 1;
  
  while (min <= max) {
    let middle = Math.floor((min + max) / 2);
    let currentElement = array[middle];
    
    if (array[middle] < val) {
      min = middle + 1;
    }
    else if (array[middle] > val) {
      max = middle - 1;
    }
    else {
      return middle;
    }
  }
  return -1;
}