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

 

// 10장 연습 문제
function sqrtIntNaive(number){
  if(number === 0 || number === 1){
    return number;
  }
  
  let index = 1, square = 1;
  
  while(square < number){
    if(square === number){
      return square;
    }
    index++;
    square = index*index;
  }
  return index;
}

sqrtIntNaive(9);

function sqrtInt(number){
  if(number === 0 || number === 1) return number;
  
  let start = 1, end = number, ans = 0;
  
  while(start <= end){
    let mid = parseInt((start + end) / 2);
    
    if(mid*mid === number) return mid;
    
    if(mid*mid < number){
      start = mid + 1;
    }else{
      end = mid - 1;
    }
    ans = mid;
  }
  
  return ans;
}

console.log(sqrtInt(9))

function findTwoSum(array, sum){
  for(let i = 0; i < array.length-1; i++){
    for(let j = i+1; j < array.length; j++){
      if(array[j] + array[i] === sum){
        return true;
      }
    }
  }
  
  return false;
}

// function findTwoSum(array, sum){
//   const store = {};
  
//   for(let i = 0; i < array.length; i++){
//     if(store[array[i]]) return true;
    
//     store[sum-array[i]] = array[i];
//   }
// }


// 선형 탐사 사용하기
function HashTable(size){
  this.size = size;
  this.keys = this.initArray(size);
  this.values = this.initArray(size);
  this.limit = 0;
}

// 선형 탐사: 인덱스가 충돌할떄 인덱스를 선형적으로 증가시키면서 사용가능한 인덱스를 찾는다
// HashTable.prototype.put = function(key, value){
//   if(this.limit >= this.size) throw 'hash table is full';
  
//   let hashedIndex = this.hash(key);
//   while(this.keys[hashedIndex] !== undefined){
//     hashedIndex++;
//     hashedIndex %= this.size;
//   }
  
//   this.keys[hashedIndex] = key;
//   this.values[hashedIndex] = value;
//   this.limit++;
// }

// HashTable.prototype.get = function(key){
//   let hashedIndex = this.hash(key);
  
//   while(this.keys[hashedIndex] !== key){
//     hashedIndex++;
//     hashedIndex %= this.size;
//   }
//   return this.values[hashedIndex];
// }

// 이차 탐사: 군집을 해결하기 좋고, 제곱을 통해서 다음키를 찾는다. 
HashTable.prototype.put = function(key, value){
  if(this.limit >= this.size) throw 'hash table is full';
  
  let hashedIndex = this.hash(key);
  let squareIndex = 1;
  
  while(this.keys[hashedIndex % this.size] !== undefined){
    hashedIndex += Math.pow(squareIndex, 2); // 제곱을 점점 더 키운다
    squareIndex++;
  }
  
  this.keys[hashedIndex % this.size] = key;
  this.values[hashedIndex % this.size] = value;
  this.limit++;
}

HashTable.prototype.get = function(key){
  let hashedIndex = this.hash(key);
  let squareIndex = 1;
  
  while(this.keys[hashedIndex % this.size] !== key){
    hashedIndex += Math.pow(squareIndex, 2);
    hashedIndex %= this.size;
    squareIndex++;
  }
  return this.values[hashedIndex % this.size];
}


// HashTable.prototype.hash = function(key){
//   if(!Number.isInteger(key)) throw 'must be int';
  
//   return key % this.size;
// }

// 이중 해싱
HashTable.prototype.hash = function(key){
  if(!Number.isInteger(key)) throw 'must be int';
  return this.secondHash(key);
}

HashTable.prototype.secondHash = function(hashedKey){
  const R = this.size - 2;
  return R - hashedKey % R;
}

HashTable.prototype.initArray = function(size){
  const array = Array.from({length: size});
  return array;
}

const exampleTable = new HashTable(13);
exampleTable.put(7, "Hi");
exampleTable.put(20, "hello");
exampleTable.put(33, "sunny");
exampleTable.put(46, "hello");
exampleTable.put(58, "hello");
exampleTable.put(72, "hello");
exampleTable.put(85, "hello");
exampleTable.put(98, "hello");

console.log(exampleTable);
exampleTable.get(20);

// 스택과 큐
function Stack(array){
  this.array = [];
  if(array) this.array = array;
}

Stack.prototype.getBuffer = function(){
  return this.array.slice();
}

Stack.prototype.isEmpty = function(){
  return this.array.length == 0;
}

Stack.prototype.peek = function(){
  return this.array[this.array.length - 1];
}

Stack.prototype.push = function(value){
  this.array.push(value);
}

Stack.prototype.pop = function(){
  return this.array.pop();
}



Stack.prototype.stackAccessNthTopNode = function(n){
  const bufferArray = this.getBuffer(); // copy뜸,  shallow copy 
  if(n <= 0) throw 'error';
  
  const bufferStack = new Stack(bufferArray);
  
  while(--n !== 0){
    bufferStack.pop();
  }
  
  return bufferStack.pop();
}

Stack.prototype.stackSearch = function(element){
  const bufferArray = this.getBuffer();
  const bufferStack = new Stack(bufferArray); // stack으로
  
  while(!bufferStack.isEmpty()){
    const cur = bufferStack.pop();

    if(cur === element){
      return true;
    }
  }
  
  return false;
}

const stack1 = new Stack();
stack1.push(10);
console.log(stack1.peek());
stack1.push(5);
console.log(stack1.peek());

console.log(stack1.stackAccessNthTopNode(2));

console.log("search", stack1.stackSearch(10));


function Queue(array){
  this.array = [];
  if(array) this.array = array;
}

Queue.prototype.getBuffer = function(){
  return this.array.slice();
}

Queue.prototype.isEmpty = function(){
  return this.array.length === 0;
}

Queue.prototype.peek = function(){
  return this.array[0];
}

Queue.prototype.enqueue = function(value){
  return this.array.push(value)
}

Queue.prototype.dequeue = function(){
  return this.array.shift();
}

Queue.prototype.queueAccessNthTopNode = function(n){
  const bufferArray = this.getBuffer();
  if(n <= 0) throw 'Error';
  
  const bufferQueue = new Queue(bufferArray);
  while(--n !== 0){
    bufferQueue.dequeue();
  }
  return bufferQueue.dequeue();
}

Queue.prototype.queueSearch = function(element){
  const bufferArray = this.getBuffer();
  
  const bufferQueue = new Queue(bufferArray);
  
  while(!bufferQueue.isEmpty()){
    if(bufferQueue.dequeue() === element){
      return true;
    }
  }
  return false;
}

// const queue1 = new Queue();
// queue1.enqueue(1);
// queue1.enqueue(2);
// queue1.enqueue(3);

// console.log(queue1);

// queue1.dequeue();
// console.log(queue1);

// queue1.dequeue();
// queue1.enqueue(4);
// queue1.enqueue(5);
// queue1.enqueue(6);
// console.log(queue1);
// console.log(queue1.queueAccessNthTopNode(2));
// console.log(queue1);

function TwoStackQueue(){
  this.inbox = new Stack();
  this.outbox = new Stack();
}

TwoStackQueue.prototype.enqueue = function(val){
  this.inbox.push(val); // 넣을때는 무조건 inbox에
}

TwoStackQueue.prototype.dequeue = function(){
  if(this.outbox.isEmpty()){
    while(!this.inbox.isEmpty()){
      this.outbox.push(this.inbox.pop());
    }
  }
  
  return this.outbox.pop();
}

const q = new TwoStackQueue();
// console.log(q.enqueue(1));
// console.log(q.enqueue(2));
// console.log(q.enqueue(3));
// console.log(q)

// console.log(q.dequeue());
// console.log(q)

// console.log(q.enqueue(3));
// console.log(q)

// console.log(q.dequeue());
// console.log(q)

// console.log(q.dequeue());
// console.log(q)

// console.log(q.dequeue());
// console.log(q);

function QueueStack(){
  this.inbox = new Queue();
}

QueueStack.prototype.push = function(val){
  this.inbox.enqueue(val);
}

QueueStack.prototype.pop = function(){
  const size = this.inbox.array.length - 1;
  let counter = 0;
  const bufferQueue = new Queue();
  while(++counter <= size){
    bufferQueue.enqueue(this.inbox.dequeue());
  }
  
  const popped = this.inbox.dequeue();
  this.inbox = bufferQueue;
  return popped
}

// const s = new QueueStack();
// s.push(1);
// s.push(2)
// s.push(3)
// s.push(4)
// s.push(5);
// console.log(s);
// console.log(s.pop(), s);
// console.log(s.pop(), s)
// console.log(s.pop(), s)
// console.log(s.pop(), s)
// console.log(s.pop(), s)

function sortableStack(size){
  this.size = size;
  this.mainStack = new Stack();
  this.sortedStack = new Stack();
  
  for(let i = 0; i < this.size; i++){
    this.mainStack.push(Math.floor(Math.random() * 11));
  }
}

sortableStack.prototype.sortStackDescending = function(){
  while(!this.mainStack.isEmpty()){
    const temp = this.mainStack.pop();
    
    while(!this.sortedStack.isEmpty() && this.sortedStack.peek() < temp){
      this.mainStack.push(this.sortedStack.pop());
      console.log("this", this);
    }
    this.sortedStack.push(temp);
  }
}

// const ss = new sortableStack(4);
// ss.sortStackDescending();


// 13장 연결 리스트
// 각 노드
function singlyLinkedListNode(data){
  this.data = data;
  this.next = null;
}

function SinglyLinkedList(){
  this.head = null;
  this.size = 0;
}

SinglyLinkedList.prototype.isEmpty = function(){
  return this.size === 0;
}

// 앞에 들어가네
SinglyLinkedList.prototype.insert = function(value){
  if(this.head === null){
    this.head = new singlyLinkedListNode(value);
  } else {
    const temp = this.head;
    this.head = new singlyLinkedListNode(value);
    this.head.next = temp;
  }
  this.size++;
}

SinglyLinkedList.prototype.remove = function(value){
  console.log("remove")
  let currentHead = this.head;
  if(currentHead.data === value){
    this.head = currentHead.next;
    this.size--;
  }else{
    let prev = currentHead;
    currentHead = currentHead.next;
    
    while(currentHead){
      if(currentHead.data === value){
        prev.next = currentHead.next; 
        break;
      }
      prev = currentHead;
      currentHead = currentHead.next;
    }
    this.size--;
  }
}

// 값에 의한 삭제
SinglyLinkedList.prototype.deleteAtHead = function(){
  let toReturn = null;
  if(this.head !== null){
    toReturn = this.head.data;
    this.head = this.head.next;
    this.size--;
  }
  return toReturn;
}

SinglyLinkedList.prototype.find = function(value){
  let currentHead = this.head;
  while(currentHead.next){
    if(currentHead.data === value){
      return true;
    }
    currentHead = currentHead.next;
  }
  return false;
}



// 이중 연결 리스트
function DoublyLinkedListNode(data){
  this.data = data;
  this.next = null;
  this.prev = null;
}

// 헤드와 테일이 있다. 
function DoublyLinkedList(){
  this.head = null;
  this.tail = null;
  this.size = 0;
}

DoublyLinkedList.prototype.isEmpty = function(){
  return this.size === 0;
}

DoublyLinkedList.prototype.insertAtHead = function(value){
  if(this.head === null){
    // 처음 집어 넣음
    this.head = new DoublyLinkedListNode(value);
    this.tail = this.head;
  }else{
    const temp = new DoublyLinkedListNode(value);
    temp.next = this.head; // 현재 head였던것 앞에다가 집어넣는거임
    this.head.prev = temp; // 현재 head였던것 앞에다가 temp의 주솟값
    this.head = temp;
  }
  
  this.size++;
}

DoublyLinkedList.prototype.insertAtTail = function(value){
  if(this.tail === null){
    this.tail = new DoublyLinkedListNode(value);
    this.head = this.tail;
  }else{
    const temp = new DoublyLinkedListNode(value);
    temp.prev = this.tail;
    this.tail.next = temp;
    this.tail = temp;
  }
  this.size++;
}

DoublyLinkedList.prototype.deleteAtHead = function(){
  let toReturn = null;
  if(this.head !== null){
    toReturn = this.head.data;
    
    if(this.tail === this.head){
      // 하나 밖에 없었던 것
      this.head = null;
      this.tail = null;
    }else{
      this.head = this.head.next;
      this.head.prev = null; // 다음게 제일 앞으로 오는것
    }
  }
  
  this.size--;
  return toReturn;
}

DoublyLinkedList.prototype.deleteAtTail = function() {
  let toReturn = null;
  if(this.tail !== null){
    toReturn = this.tail.data;
    
    if(this.tail === this.head){
      // 하나 밖에 없었던 것
      this.head = null;
      this.tail = null;
    }else{
      this.tail = this.tail.prev;
      this.tail.next = null; // 그앞에 있던게 마지막게 된다. 
    }
  }
  
  this.size--;
  return toReturn;
}

DoublyLinkedList.prototype.findStartingHead = function(value){
  let currentHead = this.head;
  while(currentHead){
    if(currentHead.data === value){
      return true;
    } 
    currentHead = currentHead.next;
  }
  
  return false;
}

DoublyLinkedList.prototype.findStartingTail = function(value){
  let currentHead = this.tail;
  while(currentHead){
    if(currentHead.data === value){
      return true;
    } 
    currentHead = currentHead.prev;
  }
  
  return false;
}

const dll1 = new DoublyLinkedList();
dll1.insertAtHead(10);
dll1.insertAtHead(12);
dll1.insertAtHead(20);
dll1.insertAtTail(10);
dll1.insertAtTail(12);
dll1.insertAtTail(20);
dll1.deleteAtTail()

dll1.findStartingHead(10);

// 단인 연결 리스트 뒤집기
function reverseSingleLinkedList(sll){
  let node = sll.head;
  let prev = null;
  
  while(node){
    const temp = node.next;
    node.next = prev;
    prev = node;
    if(!temp) break;
    node = temp;
  }
  
  return node;
}

const sll1 = new SinglyLinkedList();
sll1.insert(1);
sll1.insert(12);
sll1.insert(20);
// console.log("here", sll1)

// sll1.remove(1);
// sll1.remove(12);
// sll1.remove(20);
// console.log(sll1.deleteAtHead())
console.log("next", sll1)

console.log("converted", reverseSingleLinkedList(sll1))

// function deleteDuplicateInUnsortedSll(sll1){
//   const track = [];
//   let temp = sll1.head;
//   let prev = null;
  
//   while(temp){
//     if(track.indexOf(temp.data) >= 0){
//       prev.next = temp.next;
//       sll1.size--;
//     }else{
//       track.push(temp.data);
//       prev = temp;
//     }
//     temp = temp.next;
//   }
  
//   console.log(temp);
// }

function deleteDuplicateInUnsortedSll(sll1){
  const track = {};
  let temp = sll1.head;
  let prev = null;
  
  while(temp){
    if(track[temp.data]){
      prev.next = temp.next;
      sll1.size--;
    }else{
      track[temp.data] = true;
      prev = temp;
    }
    temp = temp.next;
  }
  
  console.log(temp);
}

C로만 링크드리스트 같은거나 해슁을 구현해봤었는데, JavaScript로 해보니가 확실히 개념자체가 너무너무 어려운것들은 아니었다는 생각도 든다. C할때는 정말 돌아버릴지도 모른다고 생각했는데, JavaScript로는 돌아버릴 정도는 아니고, 조금 까다로웠다.

웬만한건 그냥 배열로 처리하겠지만 경우에 따라서 Stack이나 Queue 생성자 함수를 만들어서 사용할때 이렇게 하면 되겠구나를 느낄수 있었던 시간. 특히 Stack두개로 Queue를 구현하고, Queue두개로 Stack을 구현하는 문제는 어려운건 아닌데, 확실히 안해봤으면 현장에서 물어볼때는 답을 하기 어려울지도 모르겠다는 생각도 든다.