자바스크립트로 하는 자료구조와 알고리즘(5장) - 배열

배열

 

삽입 : push()를 사용 / O(1)시간

삭제 :

  - pop()를 사용 / O(1)시간  , pop은 배열의 맨뒤 요소 제거

  - shift()는 맨 앞에서 제거

접근 : array[i] 로 접근

 

반복문

 

for 

while

 

for in 문 과 for of문의 차이

in앞에 지정된 변수 index는 배열의 인덱스이다.

of앞에 지정된 변수 elemnet는 배열의 항목이다.

 

 

도움 함수들 

 

.slice(begin, end)

배열의 시작 인덱스와 끝 인덱스 두 개의 매개변수를 받아서 그 시작인덱스부터 end인덱스 까지 배열의 일부를 반환

begin인덱스만 있는 경우 -> end인덱스는 배열의 최대값으로 가정

인덱스를 안주면 -> 복사본을 만든다. 하지만, 다음예제를 보면?

var array1 = [1,2,3,4]
console.log(array1.slice() === array1);  // false

** 배열의 내용이 동일하지만, 다른 주소 값을 가지므로 false이다.

 

.splice(begin, size, element1, element2...)  ** 원본 배열이 바뀜!

기존 항목을 제거하거나 신규 항목을 추가함으로써 배열의 내용을 반환하고 변경

var array = [1,2,3,4]

array.splice();  // []를 반환
array.splice(1,2); // [2,3]을 반환
array.splice(1,2,5,6,7) // [2,3]을 반환, array=[1,5,6,7,4] 가 됨

.concat()

신규 항목을 배열의 맨 뒤에 추가한 다음, 해당 배열을 반환

var array = [1,2,3,4];

array.concat();  // [1,2,3,4]
array.concat([2,3,4]);  // [1,2,3,4,2,3,4]

 

문제

 

배열 arr이 있고 어떤 수 weight가 주어졌을 때, 합쳐서 weight가 되는 배열 내 항목 두 개의 인덱스를 반환하라.
만약 합쳐서 weight가 되는 항목 두개가 존재하지 않는 경우 -1을 반환하라.

 

보통, 이중 for문을 사용하여 하나씩 비교하여 구현할 수 있지만, 시간 복잡도가 O(n^2)이 된다.

 

아래와 같이 해시테이블을 사용하여, O(n)시간에 구현 할 수 있다.

function findSumBetter(arr, weight) {
  let hashtable = {};

  for(let i=0, arrLength=arr.length; i<arrLength; i++) {
    let currentElement = arr[i];
    let difference = weight - currentElement;

      if(hashtable[currentElement] != undefined) {
        return [i, hashtable[currentElement]];
      } else {
        hashtable[difference] = i;
      }
  }
  return -1;
}

console.log(findSumBetter([1,2,3,4,5], 9));

 

 

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

let arr1 = [1, 5, 5, 10];
let arr2 = [3, 4, 5, 5, 10];
let arr3 = [5, 5, 10, 20];
let output = [5, 10];

배열의 개수가 3개이므로 k=3

 

function commonElements(kArray) {
  let hashmap = {};
  let last;
  let answer = [];

  for ( let i = 0, kArrayLength = kArray.length; i < kArrayLength; i++ ) {
    let currentArray = kArray[i];
    last = null;
    for ( let j = 0, currentArrayLen = currentArray.length; j < currentArrayLen; 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;
}

console.log(commonElements([[1, 2, 3], [1,2,3,4], [1,2]]));

 

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

 

map : 매개변수로 전달된 함수 변환을 배열의 모든 항목에 적용한 다음 변환이 적용된 항목들을 포함하는 신규 배열을 반환

 

filter : 매개변수로 전달된 조건을 충족시키는 배열들만 반환

 

reduce: 매개변수로 전달된 변환 함수를 사용해 배열의 모든 항목을 하나의 값으로 결합

**두번째 인자로 initalValue를 줄 수 있다.

 

다차원 배열

 

자바스크립트에는 다차원배열이 없다.

-> 가변 배열이 있음!

 

 

나선형으로 배열 출력하기!

 

 왼쪽에서 오른쪽으로 출력

 위에서 아래쪽으로 출력

 오른쪽에서 왼쪽으로 출력

 아래쪽에서 위쪽으로 출력

 위 4가지 출력에 대해 제한을 걸기

 

 상부 행

 하부 행

 왼쪽 열

 오른쪽 열

 이 4가지 변수를 적절히 위 출력함수들에서 써주고 증가 시키면 된다!

var 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;
  let leftCol = 0;
  let btmRow = M.length - 1;
  let 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++;
    }
  }
}

console.log(spiralPrint(M));

 

시간복잡도는 O(mn)이다. m은 열, n은 행 개수

 

 

틱택토에서 승자 맞추기

행을 먼저 확인

열을 확인

그리고 대각선 확인 (왼쪽대각선, 오른쪽 대각선)

이런식으로 하면 된다.

 

길 찾기

var board =
`%e%%%%%%%%%\n
%...%.%...%\n
%.%.%.%.%%%\n
%.%.......%\n
%.%%%%.%%.%\n
%.%.....%.%\n
%%%%%%%%%x%`

현재 위치가 x일때 e(출구)를 찾아라

 

var rows = board.split("\n");

function generateColumnArr(arr) {
    return arr.split("");
}
var mazeMatrix = rows.map(generateColumnArr);

function findChar(char, mazeMatrix) {
  var row = mazeMatrix.length,
        column = mazeMatrix[0].length;

    for (var i = 0; i < row; i++) {
        for (var j = 0; j < column; j++) {
            if (mazeMatrix[i][j] == char) {
                return [i, j];
            }
        }
    }  
}

function printMatrix(matrix) {
    var mazePrintStr = "",
        row = matrix.length,
        column = matrix[0].length;

    for (var i = 0; i < row; i++) {

        for (var j = 0; j < column; j++) {
            mazePrintStr += mazeMatrix[i][j];
        }

        mazePrintStr += "\n";

    }
    console.log(mazePrintStr);
}

function mazePathFinder(mazeMatrix) {
    var row = mazeMatrix.length,
        column = mazeMatrix[0].length,
        startPos = findChar('e', mazeMatrix),
        endPos = findChar('x', mazeMatrix);

    path(startPos[0], startPos[1]);

    function path(x, y) {
        if (x > row - 1 || y > column - 1 || x < 0 || y < 0) {
            return false;
        }
        // Found
        if (x == endPos[0] && y == endPos[1]) {
            return true;
        }
        if (mazeMatrix[x][y] == '%' || mazeMatrix[x][y] == '+') {
            return false;
        }
        // Mark the current spot
        mazeMatrix[x][y] = '+';
        printMatrix(mazeMatrix);

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

mazePathFinder(mazeMatrix);

 

 

행렬 회전

101

001

111

왼쪽으로90 도 회전해라

111

001

101

 

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

행렬의 두 번째 열이 회전된 행렬의 두 번째 행이 된다.

행렬의 첫 번째 열이 회전된 행렬의 세 번쨰 행이 된다.

 

var matrix = [[1,0,1],[0,0,1],[1,1,1]];

function rotateMatrix90Left (mat) {
  var N = mat.length;

  for(var x = 0; x <N/2; x++) {
    for(var y = x; y<N-x-1; y++){
      var temp = mat[x][y];

      mat[x][y] = mat[y][N-1-x];
      mat[y][N-1-x] = mat[N-1-x][N-1-y];
      mat[N-1-x][N-1-y] = mat[N-1-y][x];
      mat[N-1-y][x] = temp;
    }
  }
}

rotateMatrix90Left(matrix);
console.log(matrix);