큐, 덱

2023. 03. 27.

10845번 (큐)

const fs = require('fs');
const input = fs.readFileSync('./input.txt').toString().trim().split('\n');
const N = +input.shift();
const queue = [];
const answer = [];

for (let i = 0; i < N; i++) {
  if (input[i].includes('push')) {
    const num = +input[i].split(' ')[1];
    queue.push(num);
  } else if (input[i] === 'pop') {
    if (queue.length > 0) {
      answer.push(queue.shift());
    } else {
      answer.push(-1);
    }
  } else if (input[i] === 'size') {
    answer.push(queue.length);
  } else if (input[i] === 'empty') {
    if (queue.length > 0) {
      answer.push(0);
    } else {
      answer.push(1);
    }
  } else if (input[i] === 'front') {
    if (queue.length > 0) {
      answer.push(queue[0]);
    } else {
      answer.push(-1);
    }
  } else if (input[i] === 'back') {
    if (queue.length > 0) {
      answer.push(queue[queue.length - 1]);
    } else {
      answer.push(-1);
    }
  }
}

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

큐를 배열로 만들고 정답을 넣어줄 answer 배열도 만들었다.

각각의 기능들을 push, shift를 이용해 구현했다.

2164번 (카드2)

const fs = require('fs');
const input = fs.readFileSync('./dev/stdin').toString().trim();

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

class LinkedList {
  constructor() {
    this.size = 0;
    this.head = null;
    this.tail = null;
  }

  addNode(value) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
    } else {
      this.tail.next = newNode;
      newNode.prev = this.tail;
    }

    this.tail = newNode;
    this.size++;
  }

  getHead() {
    return this.head.value;
  }

  removeHead() {
    this.head = this.head.next;
    this.head.prev = null;
    this.size--;
  }

  getSize() {
    return this.size;
  }
}

const cards = new LinkedList();
for (let i = 1; i <= input; i++) {
  cards.addNode(i);
}

while (cards.getSize() !== 1) {
  cards.removeHead();
  cards.addNode(cards.getHead());
  cards.removeHead();
}

console.log(cards.getHead());

배열로 queue를 구현할 경우 shift와 push를 이용해야 하는데, 이 과정에서 시간초과가 났다.

연결리스트를 이용하여 구현한다는 것을 보고 클래스를 이용해 구현했다.

각각의 노드는 그 값을 갖고, 이전 노드와 다음 노드에 연결된다.

LinkedList에는 맨 첫번째 노드인 head와 맨 마지막 노드인 tail을 가진다.

addNode()는 특정 값을 인자로 받아 그 값을 가진 Node를 만들고, 이를 LinkedList에 추가한다.

솔직히 클래스를 이용한 연결리스트 구현은 복잡하게 생각했었는데, 한번 구현해보고 나니 머릿속에 정리가 된 것 같다.

11866번 (요세푸스 문제 0)

const fs = require('fs');
const input = fs.readFileSync('./dev/stdin').toString().trim().split(' ');

const [N, K] = input.map(Number);
const queue = [];
const answerArr = [];
let temp;

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

while (queue.length > 0) {
  for (let i = 1; i < K; i++) {
    temp = queue.shift();
    queue.push(temp);
  }
  temp = queue.shift();
  answerArr.push(temp);
}

console.log('<' + answerArr.join(', ') + '>');

우선 문제 이해가 어려웠다.

문제는 숫자들 중 K번째 인덱스가 맨 앞에 오도록 한 후 해당 숫자를 정답 배열에 넣으면 되는 내용이었다.

위 코드는 시간복잡도를 생각하지 않았는데, 일단 통과는 됐다.

queue를 1~N 까지의 숫자를 집어넣어 만들고 queue의 길이가 0이 될때까지(0보다 클 동안) K 앞의 숫자들을 꺼내어 뒤쪽으로 옮기고 shift()를 통해 정답 배열에 해당 숫자를 push했다.

1966번 (프린터 큐)

const fs = require('fs');
const input = fs.readFileSync('./dev/stdin').toString().trim().split('\n');
const caseNum = +input.shift();

for (let i = 0; i < caseNum; i++) {
  const [N, M] = input.shift().split(' ').map(Number);
  const queue = input.shift().split(' ').map(Number);
  const queueObjArr = [];
  let maxNum;
  let printedNum;
  let count = 0;

  for (let j = 0; j < N; j++) {
    queueObjArr.push({ value: queue[j], index: j });
  }

  while (true) {
    maxNum = Math.max(...queue);

    if (queue[0] >= maxNum) {
      queue.shift();
      printedNum = queueObjArr[0].index;
      queueObjArr.shift();
      count++;
    } else {
      queue.push(queue.shift());
      queueObjArr.push(queueObjArr.shift());
    }

    if (printedNum === M) {
      console.log(count);
      break;
    }
  }
}

우선 테스트 케이스의 개수만큼 for문을 반복한다.

문서의 개수 N과 몇번째로 출력되었는지 알아내야할 문서의 인덱스 M을 각각 받아온다.

각각의 값의 index는 queue가 push, shift 등의 과정을 거치면 바뀌기 때문에 처음에 객체배열 형태로 넣어 기록한다.

이후에 while문이 돌아간다.

10866번 (덱)

const fs = require('fs');
const input = fs.readFileSync('./dev/stdin').toString().trim().split('\n');

const N = +input.shift();
const deque = [];
const answerArr = [];

for (let i = 0; i < N; i++) {
  if (input[i].includes('push_back')) {
    deque.push(+input[i].split(' ')[1]);
  } else if (input[i].includes('push_front')) {
    deque.unshift(+input[i].split(' ')[1]);
  } else if (input[i] === 'pop_front') {
    if (deque.length === 0) {
      answerArr.push(-1);
    } else {
      answerArr.push(deque.shift());
    }
  } else if (input[i] === 'pop_back') {
    if (deque.length === 0) {
      answerArr.push(-1);
    } else {
      answerArr.push(deque.pop());
    }
  } else if (input[i] === 'size') {
    answerArr.push(deque.length);
  } else if (input[i] === 'empty') {
    if (deque.length === 0) {
      answerArr.push(1);
    } else {
      answerArr.push(0);
    }
  } else if (input[i] === 'front') {
    if (deque.length === 0) {
      answerArr.push(-1);
    } else {
      answerArr.push(deque[0]);
    }
  } else if (input[i] === 'back') {
    if (deque.length === 0) {
      answerArr.push(-1);
    } else {
      answerArr.push(deque[deque.length - 1]);
    }
  }
}

console.log(answerArr.join('\n'));

우선 덱이라는 것에 대해 개념을 잡았다. 스택과 큐가 섞인 개념으로 생각되었다.

각각의 기능을 push, pop, shift, unshift 등을 이용하여 구현하였다.

너무 하드코딩이라.. 이를 이용한 다른 문제를 또 풀어봐야 될 것 같다.

1021번 (회전하는 큐)

const fs = require('fs');
const input = fs.readFileSync('./dev/stdin').toString().trim().split('\n');

let N = input[0].split(' ').map(Number)[0];
const M = input[0].split(' ').map(Number)[1];
const idxArr = input[1].split(' ').map(Number);

const queue = [];
let answer = 0;

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

const leftOperator = (arr) => {
  arr.push(arr.shift());
  answer++;
};

const rightOperator = (arr) => {
  arr.unshift(arr.pop());
  answer++;
};

const getDirection = (curN, idx) => {
  if (curN / 2 >= idx) return 'left';
  return 'right';
};

for (let i = 0; i < M; i++) {
  if (getDirection(N, queue.indexOf(idxArr[i])) === 'left') {
    while (queue[0] !== idxArr[i]) leftOperator(queue);
    queue.shift();
    N--;
  } else {
    while (queue[0] !== idxArr[i]) rightOperator(queue);
    queue.shift();
    N--;
  }
}

console.log(answer);

문제 이해 자체가 쉽지 않았다.. 내가 더 잘 읽는 습관을 들여야 할 것 같다.

처음에 계속 문제가 풀리지 않았던 이유

queue라는 배열에 각 인덱스를 의미하는 요소를 push한다.

leftOperator, rightOperator는 큐를 회전시키는 함수이다.

getDirection은 어느쪽으로 돌아야 빠르게 0번 인덱스에 도달하는지를 알아내는 함수이다.

for문을 M번 실행하는데, 우선 N과 indexArr[i]의 인덱스 번호를 입력하여 getDirection을 실행한다. 여기서 왼쪽 또는 오른쪽의 방향을 얻는다.

해당 방향에 따라 0번 인덱스에 꺼내야 할 요소가 올 때까지 큐를 회전시킨다.

leftOperator, rightOperator는 한번 실행될 때마다 answer가 1씩 증가하기 때문에 이 값을 정답으로 출력한다.

5430번 (AC)

const fs = require('fs');
const input = fs.readFileSync('./dev/stdin').toString().trim().split('\n');
const T = +input.shift();
let answer = '';

for (let i = 0; i < input.length; i += 3) {
  const func = input[i].split('');
  let array = input[i + 2].replace('[', '').replace(']', '').split(',');
  let isError = false;
  let isReverse = false;

  if (input[i + 1] === '0') {
    array = [];
  }

  for (let j = 0; j < func.length; j++) {
    if (func[j] === 'R') {
      isReverse = !isReverse;
    } else {
      if (array.length > 0) {
        if (isReverse) {
          array.pop();
        } else {
          array.shift();
        }
      } else {
        isError = true;
      }
    }
  }

  answer += isError ? 'error\n' : isReverse ? `[${array.reverse()}]\n` : `[${array}]\n`;
}

console.log(answer.trim());

reverse() 메소드를 R이 등장할 때마다 사용하면 시간초과가 된다.

따라서 isReverse라는 boolean을 만들고 true이면 shift 대신 pop을 한다.

isReverse일 때는 정답을 뒤집어서 출력해야 하므로 그렇게 해준다.