자바스크립트로 보는 덱

Doozuu·2025년 12월 28일

알고리즘&자료구조 (JS)

목록 보기

27/36

덱(Deque)는 어떤 자료구조인가?

스택,큐와 유사한데 양쪽에서 데이터를 추가하고 삭제할 수 있는 자료구조이다.
Double-Ended Queue의 줄임말이다.(Deque)
필요한 프로퍼티는 큐와 동일하고, 앞에 요소를 추가하는 메서드와 뒤에 요소를 삭제하는 메서드가 추가된다.

덱은 언제 쓰이는가?

슬라이딩 윈도우와 함께 특정 구간에서 최대값/최소값 구할 때

function slidingWindowMax(arr, k) {
  const dq = new Deque();
  const result = [];

  for (let i = 0; i < arr.length; i++) {

    // 1️⃣ 윈도우 범위 벗어난 인덱스 제거
    if(dq.size() && dq.getFront() + k <= i){
      dq.deleteFront()
    }

    // 2️⃣ 뒤에서부터 현재 값보다 작은 값 제거
    while(dq.size() && arr[dq.getRear()] <= arr[i]){
      dq.deleteRear()
    }

    // 3️⃣ 현재 인덱스 삽입
    dq.addRear(i)

    // 4️⃣ 윈도우 완성 시 최댓값 기록
    if(i >= k -1){
      result.push(arr[dq.getFront()])
    }
  }

  return result;
}

덱은 어떻게 구현할 수 있는가?

프로퍼티 : 값을 저장할 객체(storage), 맨 앞을 가리키는 인덱스(front), 맨 뒤를 가리키는 인덱스(rear)
메서드 :
size : 크기 반환
addFront : 앞에 요소 추가
deleteFront : 앞의 요소 제거
getFront : 앞의 요소 반환
addRear : 뒤에 요소 추가
deleteRear : 뒤의 요소 제거
getRear : 뒤의 요소 반환

주의

deleteRear 할 때 this.rear--를 먼저 해주어야 한다는 점 (this.rear가 가리키는 것은 실제 마지막 인덱스 + 1 이기 때문)

addFront할 때 this.front--를 먼저 해주어야 한다는 점 (this.front로 값을 저장하면 현재 값을 덮어쓰기 때문)

참고
addFront할 때 this.front--를 하므로 인덱스가 음수가 될 수 있는데, 객체에서는 키가 문자열로 저장되기 때문에 인덱스가 음수가 되는 것은 문제없다.

class Deque{
  constructor(){
    this.storage = {};
    this.front = 0;
    this.rear = 0;
  }

  size(){
    return this.rear - this.front
  }

  addRear(val){
    this.storage[this.rear] = val;
    this.rear++
  }

  deleteRear(){
    if(this.size() === 0) return undefined;

    this.rear--;
    const val = this.storage[this.rear];
    delete this.storage[this.rear];

    return val;
  }

  getRear(){
    if(this.size() === 0) return undefined;
    return this.storage[this.rear - 1]
  }
  
  addFront(val){
    this.front--
    this.storage[this.front] = val;
  }

  deleteFront(){
    if(this.size() === 0) return undefined;

    const val = this.storage[this.front];
    delete this.storage[this.front];
    this.front++;

    return val
  }

  getFront(){
    return this.storage[this.front]
  }
}

const deque = new Deque();

관련 문제 풀어보기

[백준] 덱

난이도 : 실버4
문제 링크 : https://www.acmicpc.net/problem/10866

주어진 조건대로 필요한 메서드들을 정의해서 풀어주면 끝!

const fs = require('fs');
const input = fs.readFileSync(process.platform === 'linux' ? '/dev/stdin' : './test.txt').toString().trim().split('\n');
const N = +input.shift()
let answer = [];

class Deque{
  constructor(){
    this.storage = {};
    this.front = 0;
    this.rear = 0;
  }
  
  size(){
    return this.rear - this.front
  }

  push_front(val){
    this.front--;
    this.storage[this.front] = val;
  }

  push_back(val){
    this.storage[this.rear] = val;
    this.rear++
  }

  pop_front(){
    if(this.size() === 0) return -1;

    const val = this.storage[this.front]
    delete this.storage[this.front]
    this.front++

    return val
  }

  pop_back(){
    if(this.size() === 0) return -1;

    this.rear--
    const val = this.storage[this.rear]
    delete this.storage[this.rear]

    return val
  }
  
  empty(){
    return Number(this.size() === 0)
  }

  get_front(){
    if(this.size() === 0) return -1
    return this.storage[this.front]
  }

  get_back(){
    if(this.size() === 0) return -1
    return this.storage[this.rear - 1]
  }
}

const dq = new Deque();

for(let i=0;i<N;i++){
  const command = input[i].split(' ')

  if(command.length === 1){
    if(command[0] === "front"){
      answer.push(dq.get_front())
    }else if(command[0] === "back"){
      answer.push(dq.get_back())
    }else if(command[0] === "size"){
      answer.push(dq.size())
    }else if(command[0] === "empty"){
      answer.push(dq.empty())
    }else if(command[0] === "pop_front"){
      answer.push(dq.pop_front())
    }else if(command[0] === "pop_back"){
      answer.push(dq.pop_back())
    }
  }else{
    if(command[0] === "push_front"){
      dq.push_front(+command[1])
    }else if(command[0] === "push_back"){
      dq.push_back(+command[1])
    }
  }
}

console.log(answer.join('\n'))

[백준] 카드놓기

난이도 : 실버3
문제 링크 : https://www.acmicpc.net/problem/18115

명령을 거꾸로 실행해서 명령의 종류에 따라 아래 연산을 실행하면 원래 숫자를 찾을 수 있다.
1 : addFront
2 : deleteFront -> addFront -> 앞에 delete한 거 다시 addFront
3 : addRear
마지막으로 getFront를 N번 만큼 실행해주면 끝!

60%에서 시간 초과가 발생했다.
N의 최대 범위가 커서 O(n)임에도 발생했다. (객체의 delete 연산이 오래 걸리기 때문)

const fs = require('fs');
const input = fs.readFileSync(process.platform === 'linux' ? '/dev/stdin' : './test.txt').toString().trim().split('\n');
const N = +input[0]
const commands = input[1].split(' ').map(Number)
let answer = [];

class Deque{
  constructor(){
    this.storage = {};
    this.front = 0;
    this.rear = 0;
  }
  
  size(){
    return this.rear - this.front
  }

  push_front(val){
    this.front--;
    this.storage[this.front] = val;
  }

  push_back(val){
    this.storage[this.rear] = val;
    this.rear++
  }

  pop_front(){
    if(this.size() === 0) return -1;

    const val = this.storage[this.front]
    delete this.storage[this.front]
    this.front++

    return val
  }

  pop_back(){
    if(this.size() === 0) return -1;

    this.rear--
    const val = this.storage[this.rear]
    delete this.storage[this.rear]

    return val
  }
  
  empty(){
    return Number(this.size() === 0)
  }

  get_front(){
    if(this.size() === 0) return -1
    return this.storage[this.front]
  }

  get_back(){
    if(this.size() === 0) return -1
    return this.storage[this.rear - 1]
  }
}

const dq = new Deque();
let v = 1;

for(let i=N-1;i>=0;i--){
  const c = commands[i]

  if(c === 1){
    dq.push_front(v)
  }else if(c === 2){
    const t = dq.pop_front();
    dq.push_front(v)
    dq.push_front(t)
  }else if(c === 3){
    dq.push_back(v)
  }
  v++
}

for(let i=0;i<N;i++){
  answer.push(dq.pop_front())
}

console.log(answer.join(' '))

덱 대신 배열 + 인덱스 활용해서 풀었다. (아이디어 자체는 동일)

** 큐,덱에서 시간복잡도 걸릴거 같을 때는 배열 + head/tail을 사용할 것.

const fs = require('fs');
const input = fs.readFileSync(process.platform === 'linux' ? '/dev/stdin' : './test.txt').toString().trim().split('\n');
const N = +input[0]
const commands = input[1].split(' ').map(Number)

const size = 2 * N + 1;
const arr = new Array(size);
let head = N;
let tail = N;

let v = 1;

// 뒤에서부터 복원
for (let i = N - 1; i >= 0; i--) {
  const c = commands[i];

  if (c === 1) {
    arr[--head] = v;
  } 
  else if (c === 2) {
    const first = arr[head];
    arr[head] = v;
    arr[--head] = first;
  } 
  else { // c === 3
    arr[tail++] = v;
  }

  v++;
}

// 출력
let result = [];
for (let i = head; i < tail; i++) {
  result.push(arr[i]);
}

console.log(result.join(' '));

[백준] 최솟값 찾기

난이도 : 플래티넘 5
문제 링크 : https://www.acmicpc.net/problem/11003

메모리 초과가 나긴 하지만 슬라이딩 윈도우 이용해서 최소값 찾는 문제

const fs = require('fs');
const input = fs.readFileSync(process.platform === 'linux' ? '/dev/stdin' : './test.txt').toString().trim().split('\n');
const [N,L] = input[0].split(' ').map(Number)
const arr = input[1].split(' ').map(Number)
const answer = []

const size = 2 * N + 1;
const dq = new Array(size);
let head = N;
let tail = N;

function slidingWindow(arr, l){
  for(let i=0;i<N;i++){
    if(head < tail && dq[head] + l <= i){
      head++
    }

    while(head < tail && arr[dq[tail - 1]] >= arr[i]){
      tail--
    }

    dq[tail++] = i

    answer.push(arr[dq[head]])
  }
}

slidingWindow(arr,L)

console.log(answer.join(' '));

Doozuu

모든게 새롭고 재밌는 프론트엔드 새싹

이전 포스트

자바스크립트로 보는 큐

다음 포스트