[자바스크립트로하는 자료구조와 알고리즘] 1- 5장

책이 매우 좋다. 자바스크립트로 이래저래 삽질하고 해왔던 사람이라면 이책으로 내용을 다 한번 정리하면 효과가 좋을 것 같다.

// O(n)
function exampleLinear(n){
  for(let i = 0; i < n; i++){
    console.log(i);
  }
}

// O(n*n)
function exampleLinear2(n){
  for(let i = 0; i < n; i++){
    for(let j = 0; j < n; j++){
      console.log(j);
    }
  }
}

// O(n*n*n)
function exampleLinear3(n){
  for(let i = 0; i < n; i++){
    for(let j = 0; j < n; j++){
      for(let k = 0; k < n; k++){
        console.log(k);
      }
    }
  }
}

// O(logN)
function exampleLagartithmic(n){
  for(let i = 2; i <=n; i = i*2){
    console.log(i);
  }
}

// isEquivalent(a, b)
function isEquivalent(a, b){
  let aProps = Object.getOwnPropertyNames(a); // 프로퍼티만 뽑는다
  let bProps = Object.getOwnPropertyNames(b);
  
  if(aProps.length != bProps.length){
    return false;
  }
  
  for(let i = 0; i < aProps.length; i++){
    let propName = aProps[i];
    if(a[propName] !== b[propName]){
      return false;
    }
  }
  
  return true;
}

isEquivalent({'hi': 12}, {'hi': 12}); // 
console.log({'hi': 12} == {'hi': 12},{'hi': 12} === {'hi': 12}) // 메모리 주소를 비교해서 다르다고 나온다.


// 부호, 지수, 가수
// https://codetorial.net/articles/floating_point.html
// 이진수 소수점으로: https://coming1007.tistory.com/205

function numberEquals(x, y){
  return Math.abs(x-y) < Number.EPSILON; // 두개의 표현가능한 숫자 사이의 최소 차이
}

numberEquals(0.1 + 0.2, 0.3)

// 숫자 알고리즘
function isPrime(n){
  if(n <= 1) return false;
  if(n <= 3) return true;
  if(n % 2 == 0 || n % 3 == 0) return false;
  
  for(let i = 5; i * i <= n; i += 6){
    if(n % i == 0 || n % (i+2) == 0){
      return false;
    }
  }
  
  return true;
}

function primeFactors(n){
  while(n%2 == 0){
    console.log(2);
    n = n / 2;
  }
  
  for(let i = 3; i*i <= n; i+=2){
    while(n%i==0){
      console.log(i);
      n = n/i;
    }
  }
  
  if(n > 2){
    // 소수인 경우
    console.log(n);
  }
}

primeFactors(200);


function example1(base, exponent, modulus){
  return Math.pow(base, exponent) % modulus;
}

function example1_2(base, exponent, modulus){
  if(modulus === 1) return 0;
  let value = 1;
  for(let i = 0; i < exponent; i++){
    value = (value * base) % modulus;
  }
  return value;
}

function isPrime3(n){
  for(let i = 0; i <= n; i++){
    if(isPrime(i)){
      console.log(i);
    }
  }
}

isPrime3(100);

function maxDivide(number, divisor){
  while(number % divisor === 0){
    number /= divisor;
  }
  return number;
}

function isUgly(number){
  number = maxDivide(number, 2);
  number = maxDivide(number, 3);
  number = maxDivide(number, 5);
  return number === 1;
}

function arrayN(n){
  let counter = 0, currentNumber = 1, uglyNums = [];
  while(counter !== n){
    if(isUgly(currentNumber)){
      counter++;
      uglyNums.push(currentNumber);
    }
    currentNumber++;
  }
  return uglyNums;
}

arrayN(11);

'dog'.charAt(1)

'youtube'.substring(1, 2);
'youtube'.substring(3, 7);

console.log('a' < 'b') // 사전순
console.log('add' < 'b')

'Red Dragon'.indexOf('Red');
'Red Dragon'.indexOf('Blue');

function existsInString(stringValue, search){
  return stringValue.indexOf(search) !== -1;
}

console.log(existsInString('red', 'r'));
console.log(existsInString('red', 'b'));

// 문자가 몇개 등장하는지 확인
let str = "He's my king from this day until his last day";
let count = 0;
let pos = str.indexOf('a');
while(pos!== -1){
  count++;
  pos = str.indexOf('a', pos+1);
}
console.log(count);

'Red Dragon'.startsWith('Red');
'Red Dragon'.endsWith('Dragon');
'Red Dragon'.startsWith('Dragon');
'Red Dragon'.endsWith('Red');

let test1 = 'chicken,noodle,soup,broth';
test1.split(",")
test1.split("")

"Wizard of Oz".replace("Wizard", "witch");

"Apples hello apples and orange and strawberry".replace(/apples/gi, "hello")

let str1 = "JavaScript DataStructures";
let n = str1.search(/DataStructures/);
console.log(n);

function regexTest(){
  let reg = /\d+/;
  console.log(reg.test("123"));
  
  let reg2 = /^\d+$/;
  console.log(reg2.test("123a"));
  
  let reg3 = /^[0-9]*.[0-9]*[1-9]*$/ // let reg3 = /^[0-9]*.[0-9]*[1-9]+$/
  console.log("12", reg3.test("12"));
  console.log("1", reg3.test("1"));
  
}
regexTest();


let dictionary = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789".split('');
function encodeId(num){
  let base = dictionary.length;
  let encoded = '';
  if(num === 0) return dictionary[0];
  while(num > 0){
    console.log('num', num, base, num % base, Math.floor(num / base))
    encoded += dictionary[(num % base)];
    num = Math.floor(num / base);
  }
  console.log("encoded", encoded);
  return reverseWord(encoded);
}

function reverseWord(str){
  let reversed = "";
  for(let i = str.length - 1; i >= 0; i--){
    reversed += str.charAt(i);
  } 
  // 앞에있을수록 나중에 더해진 것임(reverse해서)
  return reversed;
}
function decodeId(id){
  let base = dictionary.length;
  let decoded = 0; // 마지막 몫
  for(let index = 0; index < id.split("").length; index++){
    decoded = decoded * base + dictionary.indexOf(id.charAt(index)); // 그다음 몫 + 나머지
  }
  
  return decoded;
}

console.log(encodeId(11231230));
console.log(decodeId('VhU2'))

// 자바스크립트의 배열
const arr = [1,2,3,4,5];
findSum(arr, 9);
function findSum(arr, weight){
  for(let i = 0; i < arr.length - 1; i++){
    for(let j = i;  j < arr.length; j++){
      if(arr[i] + arr[j] === weight){
        return [i, j] // [arr[i], arr[j]]; // 인덱스 반환
      }
    }
  }
  return -1;
}


function findSumBetter(arr, weight){
  const hashtable = {};
  for(let i = 0; i < arr.length; i++){
    
    let currentElem = arr[i];
    let diff = weight - currentElem; // arr[i] 가 5라면 차이가 4인 경우에는 5가 뽑혔던 것?
    
    console.log(currentElem, diff, hashtable);
    
    if(hashtable[currentElem] !== undefined){ // 차이 5를 만들었던 인덱스가 있는지(4가 차이 5를 만든다)
      return [i, hashtable[currentElem]];
    }else{
      // 차이 diff를 인덱스 i가 만든다는 것을 기록
      hashtable[diff] = i; // diff가 4일때는 4번째 요소인 5가 뽑혔던 것
    }
  }
}
console.log(findSumBetter(arr, 9));

// slice 구현
function arraySlice(array, beginIndex, endIndex){
  if(!beginIndex && !endIndex){
    return array;
  }
  
  if(!endIndex){
    endIndex = array.length;
  }
  
  const partArray = [];
  for(let i = beginIndex; i < endIndex; i++){
    partArray.push(array[i]);
  }
  return partArray;
}

arraySlice([1,2,3,4], 1,2);

// median
function medianOfArray(array){
  const length = array.length;
  if(length % 2 === 1){
    return array[Math.floor(length / 2)];
  }
  return (array[length/2] + array[length/2 - 1]) / 2;
}

function medianOfTwoSortedArray(arr1, arr2, pos){
  if(pos <= 0) return -1;
  if(pos === 1) return (arr1[0], arr2[0]) / 2;
  if(pos === 2) {
    return (Math.max(arr1[0], arr2[0]) + Math.min(arr1[1], arr2[1])) / 2
  }
  
  let median1 = medianOfArray(arr1);
  let median2 = medianOfArray(arr2);
  if(median1 === median2){
    return median1;
  }
  
  let evenOffset = pos % 2 === 0 ? 1  : 0; // 배열 짝수면 1, 홀수면 0
  let offsetMinus = Math.floor(pos/2) - evenOffset;
  let offsetPlus = pos - Math.floor(pos/2) + evenOffset;
  
  if(median1 < median2) {
    return medianOfTwoSortedArray(arr1.slice(offsetMinus), arr2.slice(0, -offsetMinus), offsetPlus);
  }else{
    return medianOfTwoSortedArray(arr2.slice(offsetMinus), arr1.slice(0, -offsetMinus), offsetPlus);
  }
}

medianOfTwoSortedArray([1,2,3], [4,5,6], 3)
medianOfTwoSortedArray([11,23,24], [32,33,450], 3)
medianOfTwoSortedArray([1,2,3], [2,3,5], 3)


function commonElements(kArray){
  let hashmap = {};
  let last = null;
  let answer = [];
  
  for(let i = 0;  i < kArray.length; i++){
    let currentArray = kArray[i];
    last = null;
    
    for(let j = 0; j < currentArray.length; j++){
      let currentElement = currentArray[j];
      if(last !== currentElement){
        if(!hashmap[currentElement]){
          hashmap[currentElement] = 1;
        }else{
          hashmap[currentElement]++;
        }
      }
      last = currentElement;
    }
  }
  
  for(let prop in hashmap){
    if(hashmap[prop] === kArray.length){
      answer.push(parseInt(prop));
    }
  }
  return answer;
}

commonElements([[1,2,3], [1,2,3,4], [1,2]]);

let M = [
  [1,2,3,4,5],
  [6,7,8,9,10],
  [11,12,13,14,15],
  [16,17,18,19,20]
]

function spiralPrint(M){
  let topRow = 0, leftCol = 0, btmRow = M.length - 1, rightCol = M[0].length - 1;
  
  while(topRow < btmRow && leftCol < rightCol){
    // 우선 시작하는 열의 column을 다 출력한다. 
    for(let col = 0; col <= rightCol; col++){
      console.log(M[topRow][col]);
    }
    // 다음행으로
    topRow++;
    
    for(let row = topRow; row <= btmRow; row++){
      console.log(M[row][rightCol]);
    }
    rightCol--;
    
    if(topRow <= btmRow){
      for(let col = rightCol; col >= 0; col--){
        console.log(M[btmRow][col]);
      }
      btmRow--;
    }
    
    if(leftCol <= rightCol){
      for(let row = btmRow; row > topRow; row--){
        console.log(M[row][leftCol]);
      }
      leftCol++;
    }
  }
}

spiralPrint(M);

function checkRow(rowArr, letter){
  for(let i = 0; i < 3; i++){
    if(rowArr[i] !== letter){
      return false;
    }
  }
  return true;
}

function checkColumn(gameBoardMatrix, columnIndex, letter){
  for(let i = 0; i < 3; i++){
    if(gameBoardMatrix[i][columnIndex] !== letter){
      return false;
    }
  }
  return true;
}

function ticTacTowWinner(gameBoardMatrix, letter){
  let rowWin = checkRow(gameBoardMatrix[0], letter) || checkRow(gameBoardMatrix[1], letter) || checkRow(gameBoardMatrix[2], letter)
  let colWin = checkColumn(gameBoardMatrix, 0, letter)  || checkColumn(gameBoardMatrix, 1, letter) ||  checkColumn(gameBoardMatrix, 2, letter)
  
  let diagonalWinLeftToRight = (gameBoardMatrix[0][0]===letter && gameBoardMatrix[1][1]===letter  && gameBoardMatrix[2][2]===letter )
  let diagonalWinRightToLeft = (gameBoardMatrix[0][2]===letter && gameBoardMatrix[1][1]===letter  && gameBoardMatrix[2][0]===letter )
  
  return rowWin || colWin || diagonalWinLeftToRight || diagonalWinRightToLeft;
}

const board = [
  ['o', '-', 'x'],
  ['-', 'o', '-'],
  ['-', 'x', 'o']
]

ticTacTowWinner(board, 'x');
ticTacTowWinner(board, 'o');