バックアップ-アルゴリズムベース1/2(200-データ構造1)

バックアップアルゴリズムベース1/2

1. 10828-スタック

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const input = [];

rl.on("line", line => {
  input.push(line);

  if (input.length >= 2 && +input[0] === input.length - 1) rl.close();
}).on("close", () => {
  input.shift();

  let index = 0;
  const array = [];
  const stack = {
    push(item) {
      array[index++] = item;
    },
    pop() {
      if(array.length === 0)  return -1
      const [item] = array.splice(--index, 1);
      return item;
    },
    size() {
      return array.length;
    },
    empty() {
      return array.length === 0 ? 1 : 0;
    },
    top() {
      return array[index - 1] || -1;
    }
  };

  
  let answer = "";

  input.forEach(v => {
    const x = v.split(" ");
    if (x[0] === "push") {
      return stack[x[0]](x[1]);
    }
    
    answer += `${stack[v]()}\n`;
  });
  
  console.log(answer);

  process.exit();
});

2.9093-单语反转

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const input = [];

rl.on("line", line => {
  input.push(line);

  if (input.length >= 2 && +input[0] === input.length - 1) rl.close();
}).on("close", () => {
  input.shift();

  let answer = "";

  input.forEach(value => {
    value.split(" ").forEach(v => {
      answer += `${v.split("").reverse().join("")} `;
    });
    answer += "\n";
  });

  console.log(answer);

  process.exit();
});

3. 9012-かっこ

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

// stack
let index = 0;
let array = [];
const stack = {
  push(item) {
    array[index++] = item;
  },
  pop() {
    if (array.length === 0) return -1;
    const [item] = array.splice(--index, 1);
    return item;
  },
  size() {
    return array.length;
  },
  empty() {
    return array.length === 0 ? 1 : 0;
  },
  top() {
    return array[index - 1] || -1;
  },
};

const input = [];

rl.on("line", line => {
  input.push(line);

  if (input.length >= 2 && +input[0] === input.length - 1) rl.close();
}).on("close", () => {
  input.shift();

  let answer = "";

  input.forEach(value => {
    const result = value.split("").some(v => {
      switch (v) {
        case "(":
          stack.push("(");
          break;
        case ")":
          // 스택이 이미 비어있다면 짝이 안맞음
          if (stack.empty()) return true;
          // 이전에 입력한 괄호가 닫는괄호라면 짝이 안맞음
          if (stack.top() === ")") return true;
          stack.pop();
          break;

        default:
          break;
      }
      return false;
    });

    // 다 끝났는데 스택이 비어있지 않다면 짝이 안맞음 ( 다음 반복을 위해 초기화함 )
    if (stack.empty()) answer += `${result ? "NO" : "YES"}\n`;
    else {
      answer += "NO\n";
      array = [];
      index = 0;
    }
  });

  console.log(answer);

  process.exit();
});

4.1874-スターク数列

私が問題を理解していないわけではありません...

5.1406-編集

最初に,Array.prototype.splice()を用いてcursor値を実現し,配列の中間を切り取り,追加する方法で実現した.
ただし、この方法を使用するとタイムアウトが発生するため、splice()を使用して配列を制御する場合は、中央で挿入または削除操作を実行すると、中央以降のすべての部分を再調整する必要があり、タイムアウトになります.
したがって、アレイ内で最も高速で最も簡単な演算Array.prototype.push()およびArray.prototype.pop()を用いて実施することができる.

白準1406 nodejsを参照

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const input = [];

rl.on("line", line => {
  input.push(line);

  if (input.length >= 2 && +input[1] === input.length - 2) rl.close();
}).on("close", () => {
  const lStack = input.shift().split("");
  const rStack = [];
  input.shift();

  input.forEach(value => {
    const [command, char] = value.split(" ");

    switch (command[0]) {
      case "L":
        if (lStack.length === 0) break;
        rStack.push(lStack.pop());
        break;
      case "D":
        if (rStack.length === 0) break;
        lStack.push(rStack.pop());
        break;
      case "B":
        lStack.pop();
        break;
      case "P":
        lStack.push(char);
        break;
      
      default:
        break;
    }
  });
  
  let answer = lStack.join("") + rStack.reverse().join("");

  console.log(answer);

  process.exit();
});

6.10845-開始

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const input = [];
let queue = [];

rl.on("line", line => {
  input.push(line);

  if (input.length >= 2 && +input[0] === input.length - 1) rl.close();
}).on("close", () => {
  input.shift();

  const commandList = [...input];

  let answer = "";

  commandList.forEach(value => {
    const [command, v] = value.split(" ");

    switch (command) {
      case "push":
        queue.push(v);
        break;
      case "pop":
        const number = queue.shift();
        answer += `${number ? number : -1}\n`;
        break;
      case "size":
        answer += `${queue.length}\n`;
        break;
      case "empty":
        answer += `${queue.length === 0 ? 1 : 0}\n`;
        break;
      case "front":
        answer += `${queue[0] ? queue[0] : -1}\n`;
        break;
      case "back":
        answer += `${queue[queue.length - 1] ? queue[queue.length - 1] : -1}\n`;
        break;
    
      default:
        break;
    }
  })

  console.log(answer);

  process.exit();
});

7.1158号-ジョセフ問題

最初はArray.prototype.pushとArray.prototype.popを用いて解くことを試みたが,インデックス値が一貫していないためshiftを用いた.

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const input = [];

rl.on("line", line => {
  input.push(line);

  rl.close();
}).on("close", () => {
  const [N, K] = input[0].split(" ").map(v => +v);

  const people = new Array(N).fill().map((v, i) => i + 1);

  const answer = [];
  
  // Queue의 원리를 이용해서 푸는 문제임
  let count = 0;
  while (people.length) {
    count++;

    // 지정된 횟수의 사람이면 제거
    if (count === K) {
      answer.push(people.shift());
      count = 0;
    }
    // 그게 아니라면 다시 맨뒤로 넣음
    else {
      people.push(people.shift());
    }
  }

  console.log("<" + answer.join(", ") + ">");

  process.exit();
});

8. 10866-デッキ

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const input = [];

rl.on("line", line => {
  input.push(line);

  if (input.length >= 2 && +input[0] === input.length - 1) rl.close();
}).on("close", () => {
  input.shift();

  const deque = [];
  let answer = "";

  input.forEach(v => {
    const [command, value] = v.split(" ");
    let temp = null;

    switch (command) {
      case "push_front":
        deque.unshift(value);
        break;
      case "push_back":
        deque.push(value);
        break;
      case "pop_front":
        temp = deque.shift() || -1;
        answer += `${temp}\n`;
        break;
      case "pop_back":
        temp = deque.pop() || -1;
        answer += `${temp}\n`;
        break;
      case "size":
        answer += `${deque.length}\n`;
        break;
      case "empty":
        temp += deque.length === 0 ? 1 : 0;
        answer += `${temp}\n`;
        break;
      case "front":
        temp = deque[0] || -1;
        answer += `${temp}\n`;
        break;
      case "back":
        temp = deque[deque.length - 1] || -1;
        answer += `${temp}\n`;
        break;

      default:
        break;
    }
  });

  console.log(answer);

  process.exit();
});