자바스크립트로 하는 자료구조와 알고리즘(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);