[node.js] 백준 2162번 카드2

1. 문제 해석

 

https://www.acmicpc.net/problem/2164

2164번: 카드2

 

자료구조 중 큐를 이용한 문제이다.

배열에 1부터 1씩 증가하는 숫자가 N개 존재하는데,

첫번째 숫자를 제거하고 두번째 숫자는 제거해서 마지막으로 옮기는것을 숫자가 한개만 남을때까지 반복한다.

 

 

2. 문제 풀이

for문을 이용해 1부터 N개까지의 배열을 만들어 주고,

배열의 길이가 1보다 크면(숫자가 1개 남기 전까지) 첫번째 숫자를 shift하고,

두번째 숫자를 push해서 맨 뒤로 넣어주고, shift하는것을 반복했더니 시간 초과가 나왔다.

 

push와 shift하는 시간은 배열을 넣고 뺄때마다 인덱스를 새로 계산해야하기 때문이다.

이 경우에는 연결리스트를 사용해 구현해줘야 한다.

연결 리스트를 사용하면 노드로 이루어져 있는데, 노드들은 링크를 이루어 리스트처럼 동작을 한다.

노드 안에는 value와 address가 있는데 value는 값을 저장하고 address는 주소로, 다음 노드를 가리킨다.

 

처음 노드를 head라 하고 마지막 노드를 tail이라고 한다.

 

 

3. 코드

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const number = Number(input);
const arr = [];

for (let i = 1; i < number + 1; i++) {
  arr.push(i);
}

while (arr.length > 1) {
  arr.shift();
  arr.push(arr[0]);
  arr.shift();
}

console.log(arr.join());

처음 구현한 시간 초과한 코드이다.

 

 

---

연결 리스트

 

연결리스트를 구현하려면 class문법을 사용해야 한다.

class문법을 직접 구현해 보는것은 처음이라서 구조부터 공부했다.

 

class는 자바스크립트 함수의 한 종류로 생각하면 된다.

같이 쓰이는 constructor 매서드는 클래스의 인스턴스 생성, 초기화하는 역할을 한다.

 

✔️ node클래스

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

각 노드는 val, next, prev의 세가지 속성을 가지고 있다.

constructor(val) 메서드는 주어진 값 val을 저장하고, next와 prev를 초기화하여 노드를 생성한다.

 

✔️ LinkedList 클래스

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

  push(val) {
    const newNode = new Node(val);

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

    this.tail = newNode;
    this.length++;

    return newNode;
  }

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

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

  getLength() {
    return this.length;
  }
}

 

 

constructor: 클래스의 생성자 메서드로 빈 리스트를 초기화한다. head, tail, length 속성을 모두 null과 0으로 설정한다.

push(val): 리스트의 끝에 새로운 노드를 추가하는 메서드이다. 주어진 값 val을 가지고 새로운 노드를 생성하고, 해당 노드를 리스트의 끝에 추가한다.

getHead(): 리스트의 첫 번째 노드의 값을 반환하는 메서드이다. 첫 번째 노드가 없는 경우(null) null을 반환한다.

removeHead(): 리스트의 첫 번째 노드를 제거하는 메서드이다. 첫 번째 노드가 있는 경우에만 동작하며, 첫 번째 노드를 삭제한 후 그 다음 노드를 새로운 첫 번째 노드로 설정한다. 이때 prev 포인터를 null로 설정하여 이전 노드와의 연결을 제거한다.

getLength(): 리스트에 포함된 노드의 수를 반환하는 메서드이다.

 

const cards = new LinkedList();

for (let i = 1; i <= N; i++) {
  cards.push(i);
}

1부터 N까지의 숫자로 이루어진 이중 연결 리스트 cards를 생성한다.

리스트에는 1부터 N까지의 숫자가 순서대로 들어간다.

 

while (cards.getLength() !== 1) {
  cards.removeHead();
  cards.push(cards.getHead());
  cards.removeHead();
}

console.log(cards.getHead());

리스트의 길이가 1이 될 때까지 작업을 반복한다.

1. 첫 번째 노드를 제거

2. 두 번째 노드를 리스트의 끝으로 옮긴다.

3. 다시 첫 번째 노드를 제거한다.

 

 이 작업은 시간초과했던 방법이랑 구현은 비슷하지만 연결 리스트를 이용해서 배열에 비해 시간을 줄였다.

 

 

class 문법을 많이 사용해보지 않아서 구조가 어색하다.

더 자주 접하고 익숙해지는 연습이 필요해보였다.