[백준] node.js/ 2164 카드2

처음 풀이 (시간 초과)

const fs = require('fs');

let input = (fs.readFileSync('./test') + '').toString().trim();

const numArr = Array.from({ length: parseInt(input) }, (v, i) => i + 1);

while (numArr.length > 1) {
  numArr.shift();
  numArr.push(numArr.shift());
}

console.log(numArr[0]);

배열을 돌며 길이가 1이될때까지

1. 첫 번째 값 제거

2. 첫 번째 값 뒤로 붙이기

반복했지만... 시간초과 

 

 

 

검색해 보니 배열의 push ,pop 을 이용하면 시간초과가 뜬다고 한다.

배열의 연산시간상  맨 앞 요소의 삭제 & 추가하는 연산이 index 수정시간하는 시간이나 다름없기 때문에

연결리스트를 만들어서 사용해야 한다는 풀이@!!

 

파이썬으로 할 땐 이런거 없었는데 ..엉엉 

 

JS는 연결리스트가 없어서 직접 만들어주면 된단다~~ 신난당!!

 

 

 

---

🤔  링크드리스트? 

링크드리스트는 노드로 이루어져 있고 val, ref,add 저장하는 공간이 있음

- find 를 위해서는 시간복잡도 O(n)

- random access를 위해서는 head에서부터 무조건 시작해 각각의 node를 탐색해야 함

- 한 쪽 방향으로만 연결되어있으면 : singly linked list  양쪽 방향 : doubly linked list (prev 방향으로도 탐색이 가능함)

 

 

그렇담 이 문제를 풀기 위해서는

배열처럼 값을 빼고 넣을때마다 인덱스를 새로계산하지 않아도 되는  링크드리스트를 직접구현해야 한다!

 

 

 

❤️  nodejs 링크드리스트

🔗 참고블로그

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
    this.prev = null;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this._size = 0;
  }

  add(value) {
    const newNode = new Node(value);

    if (!this.head) {
      this.head = newNode;
    } else {
      this.tail.next = newNode;
      newNode.prev = this.tail;
    }

    this.tail = newNode;
    this._size++;

    return newNode;
  }

  getHead() {
    return this.head.value;
  }

  removeHead() {
    this.head = this.head.next;
    this.head.prev = null;
    this._size--;
  }

  getSize() {
    return this._size;
  }
}

1. Node 클래스 생성 ( 값 , 다음값 , 이전값 )

2. LinkedList 클래스 생성 ( 헤드 , 꼬리, 크기)

3. 메서드 생성 

 - add : 값 추가

 - getHead : 현재 헤드 얻기

 - removeHead : 헤드 제거

 - getSize : 현재 사이즈

 

 

new cards

LinkedList { head: null, tail: null, _size: 0 }

초기화 cards

LinkedList {
  head: <ref *1> Node {
    value: 1,
    next: Node { value: 2, next: [Node], prev: [Circular *1] },
    prev: null
  },
  tail: <ref *2> Node {
    value: 6,
    next: null,
    prev: Node { value: 5, next: [Circular *2], prev: [Node] }
  },
  _size: 6
}

1~6의 숫자가 채워져있고 서로 연결되어 있음 (1-2-3-4-5-6)

 

 

---

 

 

 

 

 

 

다음 풀이

const fs = require('fs');

let input = (fs.readFileSync('./test') + '').toString().trim();



const cards = new LinkedList();


for (let i = 1; i <= input; i++) {
  cards.add(i);
}


while (cards.getSize() !== 1) {
  cards.removeHead();
  cards.add(cards.getHead());
  cards.removeHead();
}

console.log(cards.getHead());