[백준/nodeJS] 28279. 덱 2

안녕하세요. 박기린 입니다.

백준 28279번 덱 2 문제를 풀어보겠습니다.

 

---

문제 링크

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

28279번: 덱 2

 

 

---

문제 해석

덱(deque)을 구현하는 것이 목표입니다.

 

 

front, rear의 초기값은 -1입니다. -1은 덱 안에 아무것도 없다는 의미를 가집니다.

JS의 pop, shift, push, unshift 메소드를 사용하는 방법도 있지만, 시간초과가 됩니다. 그렇기에 front와 rear의 주소를 이용하는 방식으로 코드를 짜야 합니다.

 

 

 

값이 하나 오면 front와 rear은 0을 가리킵니다.

덱의 요소가 하나일 경우 front와 rear의 값은 동일합니다.

 

 

 

 

덱은 양방향으로 요소를 넣거나 뺄 수 있습니다.

2를 rear 쪽으로 넣는다고 하면, 덱 배열에 2를 추가한 후, rear에 +1을 해줍니다.

 

 

 

 

 

반대로 front에 값을 넣는다면 어떻게 될까요?

덱 배열의 0번 인덱스에는 이미 1이 차지하고 있습니다. 그렇다면 front 커서는 덱 배열의 맨 끝으로 갑니다.

 

덱 배열의 길이는 N으로 설정합니다. 이 문제에서 N은 입력으로 주어질 명령의 수를 의미합니다. 만약 명령이 전부 '요소를 넣는다'여도, 결국 N개를 초과하지 않습니다. 그렇기 때문에 배열의 길이는 N으로 설정합니다.

 

 

 

 

 

이제 rear 방향에서 pop을 하려고 합니다.

직접 덱 배열에서 해당 요소를 뺄 필요 없이, 그냥 rear 값만 -1해주면 됩니다.

나중에 2가 들어간 자리에 새로운 값이 들어온다면, 그냥 그대로 값을 덮어씌워서 저장하면 됩니다.

 

 

 

 

front일 경우에는 +1을 해줘야 하는데, front가 n-1이었기에 이미 배열의 끝지점인 상태였습니다.

이런 경우 조건문(if문)을 이용해서 0으로 돌아올 수 있게 지정해줍니다.

 

 

 

---

정답 코드

const fs = require("fs");
const [N, ...input] = fs
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");
const n = 1000000;
let output = "";

const deque = new Array(n);
let size = 0;
let front = -1;
let rear = -1;

const addFirst = (e) => {
  if (size === 0) {
    front = 0;
    rear = 0;
  } else {
    if (front === 0) {
      front = n - 1;
    } else {
      front--;
    }
  }

  deque[front] = e;
  size++;
};

const addLast = (e) => {
  if (size === 0) {
    front = 0;
    rear = 0;
  } else {
    if (rear === n - 1) {
      rear = 0;
    } else {
      rear++;
    }
  }

  deque[rear] = e;
  size++;
};

const removeFirst = () => {
  output += deque[front] + "\n";
  size--;
  if (front === n - 1) {
    front = 0;
  } else {
    front++;
  }
};

const removeLast = () => {
  output += deque[rear] + "\n";
  size--;

  if (rear === 0) {
    rear = n - 1;
  } else {
    rear--;
  }
};

input.forEach((e) => {
  const [exe, num] = e.split(" ").map(Number);

  if (exe === 1) {
    addFirst(num);
  }

  if (exe === 2) {
    addLast(num);
  }

  if (exe === 3) {
    size === 0 ? (output += "-1\n") : removeFirst();
  }

  if (exe === 4) {
    size === 0 ? (output += "-1\n") : removeLast();
  }

  if (exe === 5) {
    output += size + "\n";
  }

  if (exe === 6) {
    size === 0 ? (output += "1\n") : (output += "0\n");
  }

  if (exe === 7) {
    size === 0 ? (output += "-1\n") : (output += deque[front] + "\n");
  }

  if (exe === 8) {
    size === 0 ? (output += "-1\n") : (output += deque[rear] + "\n");
  }
});

console.log(output);

 

 

 

 

---

정답 코드 풀이

const fs = require("fs");
const [N, ...input] = fs
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");
const n = 1000000;
let output = "";

const deque = new Array(n);
let size = 0;
let front = -1;
let rear = -1;

n의 크기는 최대 1,000,000이기 때문에, 그냥 사전에 지정해줍니다.

덱의 크기는 n과 동일하게,

front와 rear는 덱 안에 아무것도 없다는 의미로 -1을 넣어줍니다.

size 값도 0으로 저장해줍니다.

 

 

 

 

const addFirst = (e) => {
  if (size === 0) {
    front = 0;
    rear = 0;
  } else {
    if (front === 0) {
      front = n - 1;
    } else {
      front--;
    }
  }

  deque[front] = e;
  size++;
};

const addLast = (e) => {
  if (size === 0) {
    front = 0;
    rear = 0;
  } else {
    if (rear === n - 1) {
      rear = 0;
    } else {
      rear++;
    }
  }

  deque[rear] = e;
  size++;
};

addFirst : front위치에 값을 넣습니다.

addLast : rear위치에 값을 넣습니다.

 

size가 0일 경우, 위치에 상관없이 front와 rear을 0으로 설정하고 값을 0번 인덱스에 넣어줍니다.

front의 커서가 0 or rear의 커서가 n-1인 경우에 각각 적절한 조치가 취해지게 끔 조건문을 달아줍니다.

 

 

 

 

const removeFirst = () => {
  output += deque[front] + "\n";
  size--;
  if (front === n - 1) {
    front = 0;
  } else {
    front++;
  }
};

const removeLast = () => {
  output += deque[rear] + "\n";
  size--;

  if (rear === 0) {
    rear = n - 1;
  } else {
    rear--;
  }
};

removeFirst : front위치의 값을 뺍니다.

removeLast : rear위치의 값을 뺍니다.

 

front의 커서가 n-1 or rear의 커서가 0인 경우에 각각 적절한 조치가 취해지게 끔 조건문을 달아줍니다.

 

 

 

 

 

input.forEach((e) => {
  const [exe, num] = e.split(" ").map(Number);

  if (exe === 1) {
    addFirst(num);
  }

  if (exe === 2) {
    addLast(num);
  }

  if (exe === 3) {
    size === 0 ? (output += "-1\n") : removeFirst();
  }

  if (exe === 4) {
    size === 0 ? (output += "-1\n") : removeLast();
  }

  if (exe === 5) {
    output += size + "\n";
  }

  if (exe === 6) {
    size === 0 ? (output += "1\n") : (output += "0\n");
  }

  if (exe === 7) {
    size === 0 ? (output += "-1\n") : (output += deque[front] + "\n");
  }

  if (exe === 8) {
    size === 0 ? (output += "-1\n") : (output += deque[rear] + "\n");
  }
});

입력으로 주어질 8가지 종류의 명령문을 처리하는 코드입니다.

 

 

 

 

console.log(output);

최종 결과물을 출력하면 끝입니다.