満員エレベーター

スタック・キュー・ハッシュメニュー

hogeちゃん

2023.04.25

スタック・キューメニュー応用編【3 つのスタック・レンタルビデオ店・warp・積読・満員エレベーター】

問題【STEP: 1】3 つのスタック

Task

3 つのスタック(最初は空)に対する操作の指示が与えられるので操作後の要素を出力してね。

【3 つのスタック】コード

reader.on('close', () => {
   const S = [[], [], []];  // 3つのスタック
   const N = Number(lines[0]);
   for (let i = 1; i <= N; i++) {
      const Q = lines[i].split(' ');  // 操作の指示
      switch (Q[0]) {
      case 'push':
         S[Q[1] - 1].push(Q[2]);
         break;
      case 'pop':
         S[Q[1] - 1].pop();
         break;
      }
   }
   for (let i = 0; i < 3; i++) { // 3 つのスタックに対して…
      while(S[i][0]){  // i 番目のスタックが空になるまで…
         console.log(S[i].pop());  // 末尾から取り出して 取り出した要素を出力
      }
      // while(S[i].length > 0){
        // console.log(S[i].pop());
      // }
   }
});

hogeちゃんの画像

後尾へ追加・後尾から取り出し…。
while(S[i][0])で配列が空要素になるまで処理を繰り返すことができました。

問題【STEP: 2】レンタルビデオ店

Task

ビデオの管理番号と貸出・返却の内容が与えられるので残っているビデオの番号を求めてね。

【レンタルビデオ店】コード

reader.on('close', () => {
   const N = Number(lines[0]);
   const K = Number(lines[N + 1]);
   const S = [];  // レンタルビデオの棚
   for (let i = 1; i <= N; i++) {
      const X = lines[i];
      S.unshift(X);  // 棚の先頭に配置
   }
   for (let i = N + 2; i < N + K + 2; i++) {
      const Q = lines[i].split(' ');
      switch (Q[0]) {
         case 'return':
            S.unshift(Q[1]);  // 棚の先頭に返却
            break;
         case 'rent':
            S.shift();  // 棚の先頭から貸出
            break;
      }
   }
   S.forEach(s => {
      console.log(s);  // 先頭から順に出力
   });
});

hogeちゃんの画像

先頭へ追加・先頭から取り出し…。

問題【STEP: 3】warp

Task

N 個のマスをTO[x][i]へ移動…。TO[x][i]が-1の場合 1つ戻る。止まったマスを順に出力してね。

【warp】コード

reader.on('close', () => {
   const [N, K] = lines[0].split(' ').map(Number);
   const TO = [[0]];
   for (let i = 1; i <= N; i++) {
      TO.push([0, ...lines[i].split(' ').map(Number)]);
   }
   const Move = [];  // 移動履歴
   const S = [1];  // 移動先の指示が -1 以外の移動前のマス(スタック)
   let x = 1;  // 現在のマス (1から開始)
   for (let i = 1; i <= K; i++) {
      const to = TO[x][i];  // 移動先の指示
      if (to !== -1) {  // to が -1 でない時は
         S.push(x);  // 移動前のマスに現在のマスを追加してから
         x = to;  // to に移動
         Move.push(x);  // 移動履歴に x (to)を追加
      } else {  // to が -1 の場合
         x = S.pop();  // to が -1 でなかったときの移動前のマスに一つ戻る
         Move.push(x);  // 移動履歴に x (S.pop())を追加
      }
   }
   Move.forEach(m => {
      console.log(m);
   });
});

hogeちゃんの画像

ややこしかったので配列の index とマスの番号を一致させるために TO[x][i] の先頭の値を 0 にしています。余計ややこしくなったかな? (^_^;)

問題【STEP: 4】積読

Task

本を積み重ねて上から順に読書…。未読の本の冊数と未読の合計ページ数を求めてね。

【積読】コード 1/2

reader.on('close', () => {
   const N = Number(lines[0]);
   const S = [];
   for (let i = 1; i <= N; i++) {
      const Q = lines[i].split(' ');
      switch (Q[0]) {
      case 'buy_book':
         S.push(Number(Q[1]));
         break;
      case 'read':
         let R = -(Q[1]);
         while (R <= 0) {
            R += S.pop();
         }
         if(R > 0){
            S.push(R);
         }
         break;
      }
   } 
   console.log(S.length);
   console.log(S.reduce((acc, cur) => acc + cur));
});

hogeちゃんの画像

上に積み上げて上から読書。

【積読】コード 2/2

reader.on('close', () => {
   const N = Number(lines[0]);
   let page_sum = 0;
   let book_sum = 0;
   const books = [];
   for (let i = 1; i <= N; i++) {
      const Q = lines[i].split(' ');
      switch (Q[0]) {
      case 'buy_book':
         const x = Number(Q[1]);
         book_sum++;
         page_sum += x;
         books.push(x);
         break;
      case 'read':
         let y = Number(Q[1]);
         page_sum -= y;
         while (books[books.length - 1] <= y) {
            book_sum--;
            y -= books[books.length - 1];
            books.pop();
            if (y === 0) {
               break;
            }
         }
         if (y !== 0) {
            let top = books[books.length - 1];
            books.pop();
            top -= y;
            books.push(top);
         }
      }
   }
   console.log(book_sum);
   console.log(page_sum);
});

hogeちゃんの画像

C++ の解答コード例を参照しました。

問題【FINAL】満員エレベーター

Task

EVの乗り降りに関するデータが与えられるので EV内の人数と合計体重を求めてね。

【FINAL】コード

reader.on('close', () => {
  const [N, X] = lines[0].split(' ').map(Number);
  const EV = [];
  let sum = 0;
  let num = 0;
  for (let i = 1; i <= N; i++) {
    const Q = lines[i].split(' ');
    switch (Q[0]) {
    case 'ride':
      for (let j = 2; j < Number(Q[1]) + 2; j++) {
        if (sum + Number(Q[j]) <= X) {
          sum += Number(Q[j]);
          EV.push(Number(Q[j]));
          num++;
        }
      }
      break;
    case 'get_off':
      for (let j = 0; j < Q[1]; j++) {
        sum -= EV.pop();
        num--;
      }
      break;
    }
  }
  console.log(num);
  console.log(sum);

hogeちゃんの画像

最後に乗った人から順番に降りる…。

コメント