[백준] 1021

회전하는 큐

문제

지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.

지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.

큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

풀이

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

class Deque {
  constructor() {
    this.head = new Node(-1);
    this.tail = new Node(-1);
    this.head.next = this.tail;
    this.tail.prev = this.head;
    this.size = 0;
  }
  pushFront(data) {
    let node = new Node(data);
    node.prev = this.head;
    node.next = this.head.next;
    this.head.next.prev = node;
    this.head.next = node;
    this.size++;
  }
  pushBack(data) {
    let node = new Node(data);
    node.prev = this.tail.prev;
    node.next = this.tail;
    this.tail.prev.next = node;
    this.tail.prev = node;
    this.size++;
  }
  popFront() {
    if (this.empty()) return -1;
    let tmp = this.head.next;
    this.head.next = tmp.next;
    tmp.next.prev = this.head;
    this.size--;
    return tmp.data;
  }
  popBack() {
    if (this.empty()) return -1;
    let tmp = this.tail.prev;
    this.tail.prev = tmp.prev;
    tmp.prev.next = this.tail;
    this.size--;
    return tmp.data;
  }
  returnSize() {
    return this.size;
  }
  empty() {
    return this.size ? 0 : 1;
  }
  returnFront() {
    if (this.empty()) return -1;
    return this.head.next.data;
  }
  returnBack() {
    if (this.empty()) return -1;
    return this.tail.prev.data;
  }
  findElement(n) {
    if (this.empty()) return -1;
    let tmp = this.head.next;
    let idx = 1;
    while (tmp.data !== n) {
      tmp = tmp.next;
      idx++;
    }
    return idx;
  }
}

const deque = () => {
  let input = require("fs")
    .readFileSync("/dev/stdin")
    .toString()
    .trim()
    .split("\n")
    .map((n) => n.split(" ").map(Number));
  let deq = new Deque();
  for (let i = 1; i <= input[0][0]; i++) deq.pushBack(i);
  let pushFront = 0;
  let pushBack = 0;
  let length = input[0][0];
  for (let i of input[1]) {
    let idx = deq.findElement(i);
    if (idx <= (length + 1) / 2) {
      while (deq.returnFront() !== i) {
        deq.pushBack(deq.popFront());
        pushBack++;
      }
      deq.popFront();
      length--;
    } else {
      while (deq.returnFront() !== i) {
        deq.pushFront(deq.popBack());
        pushFront++;
      }
      deq.popFront();
      length--;
    }
  }
  console.log(pushFront + pushBack);
};

deque();

반성회

덱 함수들을 구현해놓고, 매번 뽑고자 하는 원소의 인덱스를 구한 뒤 인덱스가

• 덱의 중앙보다 뒤쪽에 있을 경우 뽑으려는 원소가 맨 앞에 올 때까지 오른쪽으로 이동 (맨 뒤의 원소를 맨 앞으로 보내기 ⇒ deq.pushFront(deq.popBack());
• 덱의 중앙보다 앞쪽에 있을 경우 뽑으려는 원소가 맨 앞에 올 때까지 왼쪽으로 이동 (맨 앞의 원소를 맨 뒤로 보내기 ⇒ deq.pushBack(deq.popFront());

이때 기준을 idx <= (length + 1) / 2 로 한 이유는 idx가 0이 아닌 1부터 시작해서 length도 한 칸 밀었다

만약 (length + 1) / 2이 아닌 length / 2 일 경우 length가 홀수일 때 정확히 중앙에 있는 원소가 뒤로 밀려서 괜히 push 연산을 한번 더 해야 하는 현상이 발생

(예시: length가 9이고 idx가 5일 때, 앞의 원소 4개 뒤의 원소 4개로 덱의 중앙에 위치해있음에도 불구하고 length / 2가 4.5이기 때문에 pushBack 연산을 5번 하게 된다

하지만 pushFront 4번이면 더 빠르게 원하는 원소를 앞으로 당겨올 수 있기 때문