[백준] 2164 카드2 with JS

 

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

2164번: 카드2

문제 풀이

 

baejoon에서 저번과 같이 배열로 사용하다가 또 시간초과로 실패했다. (메모리의 크기가 상관없다면 간단하게 이렇게 풀어보는것도 좋을거 같다. -> 백준에서는 안풀림)

const fs = require("fs");
const [n] = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
//const [n] = fs.readFileSync("예제.txt").toString().trim().split("\n");

let arr = [];
for (let i = 1; i <= n; i++) {
  arr.push(i);
}
while (arr.length > 1) {
  arr.shift();
  let shift = arr.shift();
  arr.push(shift);
}
console.log(arr[0]);

저번에 공부했던 linkedList와 큐 문제를 보면서 푼다면 문제를 해결하기 쉬울 것이다.

push, shift, shiftpush, traverse 함수를 만들어 

처음에 linked list에 원소를 push

shift를 통해 앞 원소 제거(제거만 하기, 원소를 뽑는 것은 아니다.)

앞 원소를 제거하고 원소도 반환 하는 shiftpush 함수를 만들고

마지막으로 traverse  함수 내에 shift, shiftPush를 반복해서 종료 시킨다.

Class 구조 내에 this를 잘 활용해서 문제를 해결하면 좋을거 같다.

 

const fs = require("fs");
const [n] = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
//const [n] = fs.readFileSync("예제.txt").toString().trim().split("\n");
class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}
class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }

  push(value) {
    let newNode = new Node(value);

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

  shift() {
    if (!this.head) return null;
    let newNode = this.head;
    this.head = newNode.next;
  }
  shiftPush() {
    if (!this.head) return null;
    let newNode = this.head;
    let push = newNode.value;
    this.head = newNode.next;

    this.push(push);
  }
  traverse() {
    while (this.head) {
      this.shift();
      this.shiftPush();
    }
  }
}

let list = new LinkedList();

for (let i = 1; i <= n; i++) {
  list.push(i);
}

list.traverse();
console.log(list.tail.value);

 

2024.01.23 - [코딩테스트/JavaScript] - [백준] 18258번 : 큐 2 with JS

[백준] 18258번 : 큐 2 with JS