21-03-10 자바스크립트로 하는 자료구조와 알고리즘(3)

5장 자바스크립트 배열

자바스크립트의 배열은 삽입, 삭제, 접근에 O(1) 복잡도를 갖는다
삽입은 .push()나 .pop()을 사용해 배열 마지막에 추가하거나 삭제할 수 있다
array[1]과 같이 특정 인덱스에 접근한다면 메모리 주소로부터 직접 값을 얻어온다 (Java처럼 메모리 주소값을 알 수 있는 방법은 거의 없다, 스택오버플로우 참고)
n개의 항목을 방문하는 for문은 당연히도 O(n)의 시간 복잡도를 갖는다
while(true)와 같이 for( ; ;)로도 무한루프를 구현할 수 있다
for문은 for (index in arr) 이나 for (element of arr)와 같이 사용할 수 있다
일반적인 for문과 달리 forEach는 배열의 각 요소에 대해 callback을 실행하므로 중간에 break할 수 없다 (MDN 참고)
유용한 Array 내장함수

.slice(begin, end) : 얕은 복사
기존 배열을 수정하지 않고 배열의 일부분을 리턴하며 end값이 없다면 자동으로 맨 끝 인덱스로 가정한다
.splice(begin, size, element1, element2…)
첫 번째 매개변수에 지정한 값에 size만큼 잘라내고, 3번째 이후 element들이 주어졌다면 begin 인덱스부터 삽입된다
.concat()
신규 항목을 배열의 맨 뒤에 추가하고 리턴함
.length

Spread Operator : 깊은 복사

// 얕은 복사
let shallowCopy1 = [1, 2, 3];
let shallowCopy2 = shallowCopy2 // 혹은 shallowCopy1.slice();

// 깊은 복사
let deepCopy = [1, 2, 3];
let deepCopy = [...deepCopy];

배열 arr이 있고 weight가 주어졌을 때 합쳐서 weight가 되는 배열 내 항목 두 개의 인덱스를 찾기 (단, weight가 되는 두 값이 없을 경우 -1을 리턴)

const findSum = (arr, weight) => {
  for (let i = 0, arrLength = arr.length; i < arrLength; i++) {
    for (let j = i+1; j < arrLength; j++) {
      if (arr[i]+arr[j] == wieght) return [i, j]
    }
  }
  return -1;
} // n길이의 배열을 순회하는 for문이 두개 중첩되므로 시간 복잡도는 O(n의 2승)

좀 더 알아보기

const findSumBetter = (arr, weight) => {
  let hashtable = {};
  for (let i = 0, arrLength = arr.length; i < arrLength; i++) {
    let currEl = arr[i], subVal = weight - currEl;
    if (hashtable[currEl] != undefined) return [i, hashtable[currEl]]
    else hashtable[subVal] = i;
  }
  return -1;
} // 차이를 저장하고 해시테이블에 저장함으로써 O(n) 복잡도로 감소
// 대신 공간 복잡도는 O(n) (해시테이블 만큼) 으로 늘어남

두 개의 정렬된 배열이 동일한 크기일 때 해당 배열들의 중앙값 찾기

const medianOfArray = arr => {
  let len = arr.length;
  if (len % 2 === 1) return arr[Math.floor(length/2)]
  else return (arr[len/2] + arr[len/2-1])/2
}

const medianOfTwoSortedArr = (arr, arr2, pos) {
  // 배열의 길이가 0보다 같거나 작다면 -1을 리턴
  if (pos <= 0)
    return -1;
  // 배열의 길이가 1이라면 각 배열의 값을 더하고 2로 나눈 값을 리턴
  if (pos === 1) 
    return (arr[0] + arr2[0])/2
  // 배열의 길이가 2라면 0번째값의 최대값, 1번째값의 최소값을 구해 합하고 2로 나눈값을 리턴
  if (pos === 2) { 
    return (Math.max(arr[0], arr2[0]) + Math.min(arr[1], arr2[1]))/2;
  }
  // 두 배열의 중간값을 구하고
  let median = medianOfArr(arr);
  let median2 = medianOfarr(arr2);

  // 중간값이 같다면 어느 한쪽을 리턴
  if (median === median2) { 
    return median1;
  }

  // 짝수 길이의 배열이라면 offset값을 부여
  let evenOffset = pos % 2 === 0 ? 1 : 0
  // 배열 중간값을 앞뒤로 찾아보기 위해 인덱스 절반값에서 빼고 더한다
  let offsetMinus = Math.floor(pos/2) - evenOffset,
      offsetPlus = pos - Math.floor(pos/2) + evenOffset;
    
  // 첫번째 배열(arr)의 중간값이 두번째 배열(arr2)의 중간값보다 작다면
  // arr[arr[중간값], arr[중간값+1]], arr2[arr2[중간값-1], arr2[중간값]]를 매개변수로 재귀호출
  // 이 함수는 pos값이 2보다 작거나 같을 때 끝남 (분할 정복)
  if (median < median2) {
    return medianOfTwoSortedArray(arr.slice(offsetMinus), arr2.slice(0, -offsetMinus), offsetPlus);
  } else {
    return medianOfTwoSortedArray(arr2.slice(offsetMinus), arr1.slice(0, -offsetMinus), offsetPlus);
  }
} // 매번 배열을 반으로 나누므로 시간 복잡도는 O(log2(n))이다

k개의 정렬된 배열에서 공통 항목 찾기

const commonElements = kArray => {
  let hashmap = {}, last, answer = [];
  for (let i = 0, kArrLen = kArray.length; i < kArrLen; i++) {
    let currArr = kArr[i];
    last = null;
    for (let j = 0, currArrLen = currArr.length; j < currArrLen; j++) {
      let currEl = currArr[j];
      // 배열값을 받아 hashmap에 접근하여 값이 없다면 1로, 있다면 ++한다
      if (last != currArr) {
        if (!hashmap[currEl]) 
          hashmap[currEl] = 1;
        else 
          hashmap[currEl]++
      }
      // 이 배열을 정렬된 배열이므로
      // 마지막으로 꺼내온 배열의 원소를 last로 저장하여 
      // 다음 인덱스에 같은 값이 나온다면 패스하도록 설정
      last = currEl
    } 
  }

  for (let prop in hashmap) {
    // 배열의 갯수만큼 있어야 공통값임
    if (hashmap[prop] === kArray.length) 
      answer.push(parseInt(prop)) // push는 O(1)임
  }
  return answer;
} // 시간 복잡도는 O(kn)

자바스크립트 함수형 배열 메소드

map 함수는 배열을 순회하며 배열의 모든 항목에 함수를 적용하고 변화된 새 배열을 리턴함
filter 함수는 전달받은 조건을 충족시키는 요소만 있는 새 배열을 리턴함
reduce 함수는 모든 항목을 하나의 값으로 결합함

자바스크립트에는 다차원 배열이 없는 대신 가변 배열이 있다

배열의 나선형 출력
→ 왼쪽에서 오른쪽으로, 위에서 아래쪽으로, 오른쪽에서 왼쪽으로, 아래쪽에서 위로 출력하기
→ 네 가지 연산에 제한을 걸기

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

const spiralPrint = M => {
  let topRow = 0, leftCol = 0, btmRow = M.length-1, rightCol = M[0].length-1;
  while (topRow < btmRow && leftCol < rightCol) {
    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++
  }
} // 시간 복잡도 O(mn) (배열 순회이므로 이차원 배열의 m*n 크기만큼)

틱택토 게임
→ for문으로 세개의 행 모두를 확인하고 모든 열을 확인하고 대각선을 확인

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

const checkCol = (boardMatrix, colIdx, letter) => {
  for (let i = 0; i < 3; i++) {
    if(boardMatrix[i][colIdx] != letter) return false;
  }
  return true;
} // 세로

const ticTackToe = (boardMatrix, letter) => {
  let rowWin = checkRow(boardMatrix[0], letter) 
      || checkRow(boardMatrix[1], letter) 
      || checkRow(boardMatrix[2], letter) 

  let colWin = checkCol(boardMatrix, colIdx[0], letter) 
      || checkCol(boardMatrix, colIdx[1], letter) 
      || checkCol(boardMatrix, colIdx[2], letter) 
  let digonalLeft = (
    boardMatrix[0][0] == letter 
    && boardMatrix[1][1] == letter 
    && boardMatrix[2][2] == letter
  )
  let digonalRight = (
    boardMatrix[2][0] == letter
    && boardMatrix[1][1] == letter
    && boardMatrix[0][2] == letter
  )
  return rowWin || colWin || digonalLeft || digonalRight;
}

길 찾기

const findChar = (char, matrix) => {
  let row = matrix.length, col = matrix[0].length;
  for (let i = 0; i < row; i++) {
    for (let j = 0; j < col; j++) {
      if (matrix[i][j] === char) return [i,j]
    }
  }
}

const pathRinder = matrix => {
  let row = matrix.length, col = matrix[0].length;
  let start = findChar('e', matrix), end = findChar('x', matrix);
  path (start[0], start[1]);

  function path(x,y) {
    if (x - row - 1 || y > col -1 || x < 0 || y < 0) return false
    if (x === end[0] && y === end[1]) return true;
    if (matrix[x][y] == '%' || matrix[x][y] == '+') return false
    matrix[x][y] = '+';

    if (path(x, y-1) || path(x+1, y) || path(x-1, y) || path(x-1, y)) return true;
    matrix[x][y] = '.';
    return false
  }
}

행렬 회전
→ 행렬의 세 번째 열이 회전된 행렬의 첫 번째 행이 된다
→ 행렬의 두 번째 열이 회전된 행렬의 두 번째 행이 된다
→ 행렬의 첫 번째 열이 회전된 행렬의 세 번째 행이 된다

const rotateMatrix = matrix => {
  let len = matrix.length;
  for (let x = 0; x < len; x++) {
    for (let y = x; y < len - x - 1; y++){
      // 현재값을 임시로 저장
      let temp = matrix[x][y];
      // 현재 값의 오른쪽 값을 위로 옮김
      matrix[x][y] = matrix[y][len-1-x];
      // 현재 값의 아래 값을 오른쪽으로 옮김
      matrix[y][len-1-x] = matrix[len-1-x][n-1-y];
      // 현재 값의 왼쪽 값을 밑으로 옮김
      matrix[len-1-x][len-1-y] = matrix[len-1-y][x];
      // 임시변수값을 왼쪽으로 옮김
      matrix[len-1-y][x] = temp;
    }
  }
}

21-03-10 자바스크립트로 하는 자료구조와 알고리즘(3)

5장 자바스크립트 배열

Harry Kim