[백준] 11866, 요세푸스 문제0

문제 풀이

N,K가 주어졌을 때 1~N을 요소로 갖는 배열을 만든 다음 K 번째에 위치하는 요소를 순차적으로 제거하는 문제다.
처음에 직관적으로 K번째 요소를 제거하는 부분을 splice 배열 메소드를 사용해서 제거하는 방법으로 하려고 했었는데 매번 제거해야하는 인덱스를 설정하는 규칙을 만들어주는 부분이 굉장히 까다로웠다.

그래서 문제 접근 방법 자체를 K 번째 위치하는 요소를 제거하는 것이 아니라 큐의 요소들을 K-1번 회전시켜서 head위치에 K번째 요소를 가져온 다음 제거하는 식으로 문제를 해결했다.

자바스크립트 배열을 사용하면 가장 맨 처음 요소를 제거하는 shift 메소드를 사용해야 하는데 시간복잡도가 O(n)이기 때문에 직접 구현한 연결리스트를 사용해서 시간복잡도를 낮췄다.

제출 코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const [N, K] = fs.readFileSync(filePath).toString().trim().split(" ").map(Number);
class Node {
  constructor(data) {
    this.data = data;
    this.prev = null;
    this.next = null;
  }
}

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

  unshift(data) {
    const node = new Node(data);

    if (this.head === null) {
      this.head = node;
      this.tail = node;
    } else {
      node.next = this.head;
      this.head.prev = node;
      this.head = node;
    }
    this.length++;
  }

  push(data) {
    const node = new Node(data);

    if (this.tail === null) {
      this.tail = node;
      this.head = node;
    } else {
      node.prev = this.tail;
      this.tail.next = node;
      this.tail = node;
    }
    this.length++;
  }

  shift() {
    if (this.head === null) {
      return;
    }

    const head = this.head;
    if (this.length === 1) {
      this.head = null;
      this.tail = null;
      this.length--;
    } else {
      this.head = this.head.next;
      this.head.prev = null;
      this.length--;
    }

    return head;
  }

  pop() {
    if (this.tail === null) {
      return;
    }

    const tail = this.tail;
    this.tail = this.tail.prev;
    this.tail.next = null;
    this.length--;

    return tail;
  }

  insert(data, index) {
    if (index < 0 || index > this.length) {
      console.log("invaild index");
      return;
    }

    if (index === 0) {
      this.unshift(data);
      return;
    }

    if (index === this.length) {
      this.push(data);
      return;
    }

    const node = new Node(data);
    let pointer = 0;
    let current = this.head;
    let before;

    while (pointer < index) {
      pointer++;
      before = current;
      current = current.next;
    }
    node.next = current;
    node.prev = before;
    before.next = node;
    current.prev = node;
    this.length++;
  }

  delete(index) {
    if (index < 0 || index > this.length - 1) {
      console.log("invalid index");
      return;
    }

    if (index === 0) {
      this.head = this.head.next;
      this.head.prev = null;
      this.length--;
      return;
    }

    if (index === this.length - 1) {
      this.tail = this.tail.prev;
      this.tail.next = null;
      this.length--;
      return;
    }

    let current = this.head;
    let before;
    let pointer = 0;

    while (pointer < index) {
      pointer++;
      before = current;
      current = current.next;
    }

    before.next = current.next;
    before.next.prev = before;
    this.length--;
  }

  print() {
    const list = [];
    let current = this.head;

    while (current) {
      list.push({
        data: current.data,
        prev: current.prev?.data,
        next: current.next?.data,
      });
      current = current.next;
    }

    console.log(list);
  }
}

const queue = new DoublyLinkedList();
for (let i = 1; i <= N; i++) {
  queue.push(i);
}

const answer = [];

while (queue.length > 0) {
  for (let i = 0; i < K - 1; i++) {
    const head = queue.shift();
    queue.push(head.data);
  }
  const head = queue.shift();
  answer.push(head.data);
}
console.log("<" + answer.join(", ") + ">");

출처
요세푸스 문제0 https://www.acmicpc.net/problem/11866