Frequency Counters
자바스크립트의 객체를 이용해서 다양한 값과 빈도를 수집한다.
이 패턴은 알고리즘과 과제에 있는 여러 데이터와 입력값이
서로 비슷한 값으로 구성되어 있는지, 서로 간의 아나그램인지,
값이 다른 값에 포함되는지 여부를 비교하거나, 데이터를 입력값이나 두 개 이상의 빈도
혹은 특정하게 발생하는 빈도와 비교할 때 유용하다.
ex1. 2개의 배열을 허용하는 same이라는 함수를 작성하십시오.
배열의 모든 값이 2개의 배열을 허용하는 same이라는 함수를 작성하십시오.
배열의 모든 값이 두 번째 배열에 해당하는 값을 가지면 true를 반환해야 한다.
// same([1,2,3], [4,1,9]) -> true
// same([1,2,3], [1,9]) -> false
// same([1,2,1], [4,4,1]) -> false (must be same frequency)// naive solution
function same(arr1, arr2) {
if (arr1.length !== arr2.length) {
return false;
}
for (let i = 0; i < arr1.length; i++) {
let correctIndex = arr2.indexOf(arr1[i] ** 2)
if (correctIndex === -1 ) {
return false;
}
arr.splice(correctIndex, 1);
}
return true;
}
// Time Complexity - N^2
// Refactored
function same(arr1, arr2) {
if (arr1.length !== arr2.length) {
return false;
}
let frequencyCounter1 = {}
let frequencyCounter2 = {}
for (let val of arr1) {
frequencyCounter1[val] = (frequencyCounter1[val] || 0) + 1
}
for (let val of arr2) {
frequencyCounter2[val] = (frequencyCounter2[val] || 0) + 1
}
for (let key in frequencyCounter1) {
if(!(key ** 2 in frequencyCounter2)) {
return false;
}
if(frequencyCounter2[key ** 2] !== frequencyCounter1[key]) {
return false;
}
}
return true;
}
// Time Complexity - N빈도 카운터 패턴이 사용된 코드이다.
각 배열에 한 번씩 개별적으로 루프를 적용할 수 있다.
두 개의 루프가 두 개의 중첩된 개별 루프보다 훨씬 낫다!
ex2. Anagrams
두 개의 문자열을 취하여 두 문자열이 서로의 아나그램이면 true가 반환된다.
// validAnagram('', '') -> true
// validAnagram('aaz', 'zza') -> false
// validAnagram('anagram', 'nagaram') -> true
// validAnagram('rat', 'car') -> false
// validAnagram('awesome', 'awesom') -> false
// validAnagram('qwerty', 'qeywrt') -> true
// validAnagram('texttwisttime', 'timetwisttext') -> truefunction validAnagram (first, second) {
if (first.length !== second.length) {
return false;
}
const lookup = {};
for (let i = 0; i < first.length; i++) {
let letter = first[i];
lookup[letter] ? lookup[letter] += 1 : lookup[letter] = 1;
}
console.log(lookup);
for (let i = 0; i < second.length; i++) {
let letter = second[i];
if (!lookup[letter]) {
return false;
} else {
lookup[letter] -= 1;
}
}
return true;
}
validAnagram('texttwisttime', 'timetwisttext');Multiple Pointers
이 패턴의 개념은 인덱스나 위치에 해당하는 포인터나 값을 만든 다음 특정 조건에 따라
중간 지점에서부터 시작 지점이나 끝 지점이나 양쪽 지점을 향해 이동시키는 것이다.
ex1. 정렬된 배열을 취하는 sumZero라는 함수를 작성하자.
분류가 아니라 정렬된 배열이어야 한다. 다만 오름차순이다.
sumZero([-3, -2, -1, 0, 1, 2, 3]) // [-3, 3]
sumzero([-2,0,1,3]) // undefined
sumzero([1,2,3]) // undefined// Naive Solution
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]];
}
}
}
}
// Time Complexity - O(N^2)
// Space Complexity - O(1)
다중 포인터를 사용하면 중첩된 루프를 사용하고 여기서 시작하여 각각의 모든 숫자를 찾아 이동하고 또 모든 숫자를 찾아야 하는 작업보다는 훨씬 작업이 줄어든다.
// Refactored
function sumZero2(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++;
}
}
}
// Time Complexity - O(N)
// Space Complexity - O(1)리팩토링된 코드다. 하나는 왼쪽에서 0의 위치에서 시작하고 다른 하나는 배열의 마지막 위치에서 시작한다.
CountUniqueValue
ex. 배열을 주면 배열에 몇 개의 수가 들어있는지 고유한 수를 센다
// countUniqueValue([1,1,1,1,1,2]) // 2
// countUniqueValue([1,2,3,4,4,4,7,7,12,12,13]) // 8
// countUniqueValue([]) // 0
// countUniqueValue([-2,-1,-1,0,1]) // 4[a,b,c,d]에서 a에 i, b에서 j가 시작한다. i와 j가 다르면 j위치로 i를 이동시키고 다시 j를 보낸다. 이렇게 해서 i가 몇번째 인덱스인지 확인하면 고유한 수를 셀 수 있을 것이다.
function countUniqueValues(arr) {
if (arr.length == 0) return 0;
var i = 0;
for (let j = 0; j < arr.length; j++) {
if (arr[i] !== arr[j]) {
i++;
arr[i] = arr[j];
}
}
return i + 1;
}
// Time Complexity - O(n)
// Space Complexity - O(n)Sliding Window
배열이나 문자열과 같은 일련의 데이터를 입력하거나 특정 방식으로 연속적인 해당 데이터의 하위 집합을 찾는 경우에 유용하다.
ex1. maxSubarraySum
배열과 숫자 하나를 전달하고 서로 마주한 두 숫자의 가장 큰 합계를 찾으시오.
// maxSubarraySum([1,2,5,2,8,1,5],2) // 10
// maxSubarraySum([1,2,5,2,8,1,5],4) // 17
// maxSubarraySum([4,2,1,6],1) // 10
// maxSubarraySum([4,2,1,6,2],4) // 13
// maxSubarraySum([],4) // null// Naive solution
function maxSubarraySum(arr, num) {
if (num > arr.length) {
return null;
}
var max = -Infinity;
for (let i = 0; i < arr.length - num + 1; i++) {
temp = 0;
for (let j = 0; j < num; j++) {
temp += arr[i+j];
}
if (temp > max) {
max = temp
}
}
return max;
}
// Time Complexity - O(N^2)
// Refactored
function maxSubarraySum2(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;
}
// Time Complexity - O(N)
Divide and Conquer
이 알고리즘은 주로 배열이나 문자열 같은 큰 규모의 데이터셋을 처리한다.
ex1. 주어진 정수들이 정렬된 배열에 있을 때, 'search'라는 함수를 작성한다.
이 함수는 값 하나를 받아들이고, 해당 값이 있는 위치의 인덱스를 반환해야 한다. 만약 값이 배열 안에 없으면 -1을 반환해야 한다.
// search([1,2,3,4,5,6],4) // 3
// search([1,2,3,4,5,6],6) // 5
// search([1,2,3,4,5,6],11) // -1// naive solution
function search(arr, val) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === val) {
return i;
}
}
return -1;
}
// time complexity - O(N)
// Refactored
function search2 (arraym, 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;
}