큐, 덱


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일 때는 정답을 뒤집어서 출력해야 하므로 그렇게 해준다.