[TIL] DAY20_JS_1. 공부해야될 자료구조, 2. 배열과 리스트, 3. Making a 15 puzzle

Friday. November 10, 2017 - 7 mins

Summary:

DAY20

20171110

TIL

#1. 자료구조 공부해야할 것!

list
map(딕셔너리, 오브젝트)
tree
graph

#2. 배열과 리스트(list)

1. 배열 VS 리스트 (배열과 리스트의 차이는?)

먼저, 배열이나 리스트는 언제 사용할까?
1. 임의의 원소를 자주 읽을 때 = random access
2. 만약에 삽입이 빈번하게 일어난다면
  - 배열보다는 링크드 리스트라는 걸 많이 사용한다.

배열

크기가 고정되어 있다.
특정 원소에 접근 복잡도 : O(1) //a[0]
특정 원소의 값을 바꾸기 : O(1) //a[0] = 5;

원소 삽입의 복잡도 : O(n)

//n자리에 x값을 넣는다.
arr.length++;
for(i = arr.length - 1; i >= n; i--) {
  arr[i] = arr[i - 1];
}

배열 메소드

init(size)
write(idx, value)
read(idx)
length()
addFirst(value)
addLast(value)
removeFirst() //return first calue
removeLast()
slice(start, end)

구현해보기

var myArray = function(size) {
  this.array = [];
  this.array.length = size;
};
myArray.prototype.write = function(idx, value) {
  this.array[idx] = value;
};
myArray.prototype.read = function(idx) {
  return this.array[idx];
};
myArray.prototype.length = function() {
  return this.array.length;
};
myArray.prototype.addFirst = function(value){
  for(var i = this.array.length - 1; i > 0; i--) {
    this.array[i] = this.array[i - 1];
  }
  this.array[0] = value;
};
myArray.prototype.addLast = function(value) {
  this.array.length++;
  this.array[this.array.length] = value;
};

var arr = new myArray(5);
arr.addFirst(1);
arr.addLast(4);
console.log(arr);

리스트 : 크기가 가변적이다.(확장/축소 가능)

크기가 가변적이다.(확장& 축소가 가능하다.)

리스트 구현하기

var Node = function(v) {
  this.value = v;
  this.next = null;
};
var head = new Node(1);
Node.prototype.append = function(v) {
  var n = new Node(v);
  n.next = this.next;
  this.next = n;
};
head.append(2);
console.log(head);
// head = {v : 1, next : {v : 3, next : null}};

addLast 구현하기

var Node = function(v) {
  this.value = v;
  this.next = null;
};
var head = new Node(1);
Node.prototype.append = function(v) {
  var n = new Node(v);
  n.next = this.next;
  this.next = n;
};
Node.prototype.addLast = function(v) {
  var curr = this.next;
  while(curr.next != null) {
    curr = curr.next;
  }
  curr.append(v);
};
head.append(2); //1 - 2
head.append(3); //1 - 3 - 2
head.append(5); // 1 - 5 - 3 - 2
head.addLast(4); //
console.log(head);

My Coding

Making a 15 puzzle

My solution ```javascript //display moves start var moves = 0; var textMoves; textMoves = document.getElementById(‘textMoves’); textMoves.innerHTML = moves; //display moves end //variables start var n_00, n_01, n_02, n_03, n_10, n_11, n_12, n_13, n_20, n_21, n_22, n_23, n_30, n_31, n_32, n_33; var nArray = [[n_00, n_01, n_02, n_03], [n_10, n_11, n_12, n_13], [n_20, n_21, n_22, n_23], [n_30, n_31, n_32, n_33]]; var numArray = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0]; var colum = 4; //varatibales end //tile start function mkTile() { for (var i = 0; i < 4; i++) { for (var j = 0; j < 4; j++) { nArray[i][j] = document.getElementById(“n” + i + j); (function(m,n) { nArray[i][j].onclick = function() { clickTile(m, n); }; })(i,j); } } }

function shuffleTile() {
  var idx = 0;
  // numArray.sort(function(a, b) {
  //   return 0.5 - Math.random();
  // });
  for (var i = 0; i < 4; i++) {
    for (var j = 0; j < 4; j++) {
      nArray[i][j].innerHTML = numArray[idx];
      idx++;
    }
  }
}
function showTile() {
  for (var i = 0; i < 4; i++) {
    for (var j = 0; j < 4; j++) {
      nArray[i][j] = document.getElementById("n" + i + j);
    }
  }
}
function clickTile(x1, y1) {
    console.log(x1,y1);
    console.log(nArray[x1][y1]);
    console.log(nArray);
    if (x1 > 0 && nArray[x1 - 1][y1].innerHTML === '0') {  //up
    tileSwap(nArray, x1, y1, x1 - 1, y1);
    return true;
  } else if ( y1 > 0 && nArray[x1][y1 - 1].innerHTML === '0') { //left
    tileSwap(nArray, x1, y1, x1, y1 - 1);
    return true;
  } else if (y1 < 3 && nArray[x1][y1 + 1].innerHTML === '0') { //right
    tileSwap(nArray, x1, y1, x1, y1 + 1);
    return true;
  } else if (x1 < 3 && nArray[x1 + 1][y1].innerHTML === '0') { //down
    tileSwap(nArray, x1, y1, x1 + 1, y1);
    return true;
  } else {
    return false;
  }
}
function tileSwap(arr, x1, y1, x2, y2) {
  // var temp;
  // temp = arr[x1][y1];
  // arr[x1][y1] = arr[x2][y2];
  // arr[x2][y2] = temp;
  var temp;
  temp = arr[x1][y1].innerHTML;
  arr[x1][y1].innerHTML = arr[x2][y2].innerHTML;
  arr[x2][y2].innerHTML = temp;
}
//tile end
// function arrayMove(arr, x1, y1, position) {
//   if(position === "left" && y1 > 0) {
//     arraySwap(arr, x1, y1, x1, y1 - 1);
//     return true;
//   } else if(position === "right" && y1 < 3) {
//     arraySwap(arr, x1, y1, x1, y1 + 1);
//     return true;
//   } else if(position === "up" && x1 > 0) {
//     arraySwap(arr, x1, y1, x1 - 1, y1);
//     return true;
//   } else if(position === "down" && x1 < 3) {
//     arraySwap(arr, x1, y1, x1 + 1, y1);
//     return true;
//   } else {
//     return false;
//   }
// }
//main start
mkTile();
shuffleTile();

  ```html
        <!DOCTYPE html>
        <html lang="en">
        <head>
          <meta charset="UTF-8"> <link rel="stylesheet" href="./mkNumPuzzle.css">
          <meta name="viewport" content="width=device-width, initial-scale=1.0">
          <meta http-equiv="X-UA-Compatible" content="ie=edge">
          <title>Making a puzzle</title>
        </head>
        <body>
          <div id = "puzzle">

            <div><span id = "n00"></span><span id = "n01"></span><span id = "n02"></span><span id = "n03"></span></div>
            <div><span id = "n10"></span><span id = "n11"></span><span id = "n12"></span><span id = "n13"></span></div>
            <div><span id = "n20"></span><span id = "n21"></span><span id = "n22"></span><span id = "n23"></span></div>
            <div><span id = "n30"></span><span id = "n31"></span><span id = "n32"></span><span id = "n33"></span></div>

            <div id = "textMoves">  </div>
          </div>
          <script src="mkNumPuzzle.js"> </script>
        </body>
        </html>
    ```
    ```css
    span {
      background-color: white;
      display : inline-block;
      color : orange;
      font-family: verdana;
      text-align: center;
      font-size: 20px;
      width : 40px;
      height: 40px;
      border: 1px solid #222;
    }
    body {
      background-color : green;
    }

Jaewook Kwon

dreaming a iOS developer