문제

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

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

1. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
2. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
3. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.

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

입력

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

출력

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

예제 입력

10 3
2 9 5

예제 출력

8

내가 했던 풀이 방법

※ 해당 문제는 Deque를 이용하여 풀이하였으며, Deque 구현은 [알고리즘/자료구조] JavaScript 덱(Deque) 구현하기를 참고하여 구현했습니다.

1. 첫 번째 줄의 값을 공백으로 분할하여 N과 M에 저장해주고, 두 번째 줄의 값을 공백으로 분할하여 array 배열에 저장해준다.
2. class를 이용해 Deque를 구현해준 뒤, 1부터 N까지 push_back을 이용하여 Deque에 더해준다.
3. getFront()를 이용해 Deque에 head에 있는 값을 가져온다. 해당 값이 array[index]에 있는 값과 같을 경우, pop_front를 통해 1번 연산을 수행해준 뒤, index를 1씩 증가시켜준다. (제출 후에 알게된 것이지만, remove 변수를 사용 할 필요가 없다.)
4. array[index] 값과 다를 경우, find(array[index])를 통해 deque에서 다음으로 뽑아내야 할 값의 위치를 가져온다. 해당 값이 현재 deque의 크기/2보다 같거나 작을 경우, 2번 연산을 반복해주는 것이 가장 빠르므로 push_back을 수행해준다. 클 경우에는 3번 연산 즉, push_front를 해준다. push_back 또는 push_front를 수행해준 뒤 count를 1씩 증가시켜준다. (제출 후에 알게된 것이지만, 해당 코드대로 하면 find를 쓸데없이 자주 사용하게 되므로, find 반환 값-1만큼 push해주도록 수정하는 것이 좋을 것 같다.)
5. index가 M이 될 때(현 코드에서는 remove)까지 3~4번을 반복해준 뒤, count를 출력해준다.

코드

const fs = require('fs');
let [n, input] = fs.readFileSync(0, 'utf-8').toString().trim().split('\n');

let N = Number(n.trim().split(' ')[0]);
let M = Number(n.trim().split(' ')[1]);

const array = input.trim().split(' ').map(Number);

class Deque {
  constructor() {
    (this.storage = []), (this.head = 0), (this.tail = 0);
  }

  push_front(value) {
    if (this.storage[0]) {
      for (let i = this.storage.length; i > 0; i--) {
        this.storage[i] = this.storage[i - 1];
      }
    }
    this.storage[this.head] = value;
    this.tail++;
  }

  push_back(value) {
    this.storage[this.tail++] = value;
  }
  
  pop_front() {
    if (this.tail <= this.head) {
      return null;
    }
    return this.storage[this.head++];
  }

  pop_back() {
    if (this.tail <= this.head) {
      return null;
    }
    return this.storage[--this.tail];
  }
  
  getFront() {
    return this.storage[this.head];
  }

  find(value) {
    let count = 0;
    for (let i = this.head; i < this.tail; i++) {
      if (this.storage[i] === value) {
        return count;
      }
      count++;
    }
    return null;
  }

  size() {
    return this.tail - this.head;
  }
}

let deque = new Deque();
for (let i = 1; i <= N; i++) {
  deque.push_back(i);
}

let remove = 0;
let num = 0;
let index = 0;
let count = 0;

while (true) {
  if (remove === M) break;
  num = deque.getFront();
  if (num === array[index]) {
    deque.pop_front();
    index++;
    remove++;
  } else {
    if (deque.find(array[index]) <= deque.size() / 2) {
      deque.push_back(deque.pop_front());
    } else {
      deque.push_front(deque.pop_back());
    }
    count++;
  }
}

console.log(count);

회고

어려운 문제는 아니였지만, 덱을 구현하는 것에서 시간을 많이 쓰게 됐다. (queue보다 신경쓸 게 없긴하지만, 처음에는 storage를 객체로 구현했는데 push_front에서 복잡해져서 배열로 교체하는 등.. 은근 어려웠다.) 제출하고보니 코드 자체가 아쉬운 게 많다. 풀이 방법에서 서술했듯이 불필요한 변수 사용 등 아쉬운 점이 많지만.. 그래도 덱을 구현하니 굉장히 뿌듯했다. ㅎㅎ