[Javascript/자바스크립트] 백준 1158번 요세푸스 문제

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

코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "dev/stdin" : "input.txt";
const [n, k] = fs
  .readFileSync(filePath)
  .toString()
  .trim()
  .split(" ")
  .map((item) => +item);

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

  setPrev(prev) {
    this.prev = prev;
  }

  setNext(next) {
    this.next = next;
  }

  getValue() {
    return this.value;
  }
}

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

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

  push(value) {
    const newNode = new Node(value);
    if (this.rear) {
      this.head.setPrev(newNode);
      this.rear.setNext(newNode);
      newNode.setPrev(this.rear);
      newNode.setNext(this.head);
    } else {
      newNode.setNext(newNode);
      newNode.setPrev(newNode);
      this.head = newNode;
    }
    this.rear = newNode;
    this.size++;
  }

  popNthFromHead(n) {
    for (let i = 0; i < n; i++) {
      this.head = this.head.next;
    }
    const poppedNode = this.head.prev;
    this.head.setPrev(poppedNode.prev);
    poppedNode.prev.setNext(this.head);
    this.size--;
    return poppedNode.getValue();
  }
}

function solution(n, k) {
  const answer = [];
  const doublyLL = new DoublyLinkedList();

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

  while (!doublyLL.isEmpty()) {
    answer.push(doublyLL.popNthFromHead(k));
  }

  return "<" + answer.join(", ") + ">";
}

console.log(solution(n, k));

풀이

사실 이렇게 이중 연결리스트 구현해서 할 필요는 없다.

배열을 사용하고, 배열에서 삭제할 원소를 `splice`로 삭제하는 방법이 더 간편하긴 하다. 배열 사용 풀이

 

더 간단한 방법이 있는데 왜 이렇게 했냐면....그냥 해보고 싶어서 구현해봤다.

어제의 문제 풀이에서는 Deque를 자바스크립트로 구현해보며 단방향 연결리스트를 사용했는데, 여기서는 이중 연결 리스트를 사용해볼 수 있겠다는 생각이 들어서 활용해봤다.

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

  setPrev(prev) {
    this.prev = prev;
  }

  setNext(next) {
    this.next = next;
  }

  getValue() {
    return this.value;
  }
}

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

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

  push(value) {
    const newNode = new Node(value);
    if (this.rear) {
      this.head.setPrev(newNode);
      this.rear.setNext(newNode);
      newNode.setPrev(this.rear);
      newNode.setNext(this.head);
    } else {
      newNode.setNext(newNode);
      newNode.setPrev(newNode);
      this.head = newNode;
    }
    this.rear = newNode;
    this.size++;
  }

  popNthFromHead(n) {
    for (let i = 0; i < n; i++) {
      this.head = this.head.next;
    }
    const poppedNode = this.head.prev;
    this.head.setPrev(poppedNode.prev);
    poppedNode.prev.setNext(this.head);
    this.size--;
    return poppedNode.getValue();
  }
}

 

DoublyLinkedList가 이중 연결 리스트를 생성하기 위한 클래스이다.

여기서는 메서드를 구현할 때, 보편적인 이중 연결 리스트의 메서드를 구현하기보다는 요세푸스 문제만을 위한 메서드들을 만들어서 사용했다. `popNthFromHead`는 현재 head가 가리키는 노드에서부터 n번째 떨어진 노드를 pop하는 메서드이다. 

 

function solution(n, k) {
  const answer = [];
  const doublyLL = new DoublyLinkedList();

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

  while (!doublyLL.isEmpty()) {
    answer.push(doublyLL.popNthFromHead(k));
  }

  return "<" + answer.join(", ") + ">";
}

console.log(solution(n, k));

 

1. 구현해놓은 DoublyLinkedList를 생성하고, 여기에 1부터 N까지 순차적으로 push하여 문제 풀이에 필요한 이중 연결 리스트를 만든다.

2. 이중 연결리스트(`doublyLL`)이 빌 때까지 `popNthFromHead` 메서드를 실행하여 K번째 사람을 제거하는 과정을 반복한다.