paizaラーニング レベルアップ問題集 ソートメニュー応用編 JavaScript 辞書順

辞書順 (paizaランク C 相当)

JavaScriptで解いてみました。

問題文の例で、abc, aa, a, abの四つが出てきていますが、アルファベット小文字 3 文字で作れる文字列なので、aaやa,abは考える必要はありません。辞書順で最初はaaaから、最後はzzzまでを考えれば良いです。

アルファベット小文字 3 文字で作れる文字列を全パターン作成し、辞書順にソートしてから k 番目の文字列を出力します。

JavaScript

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

const k = Number(lines[0]);
const alphabet = "abcdefghijklmnopqrstuvwxyz";
let words = [];
  for (let c1 = 0; c1 < alphabet.length; c1++) {
    for (let c2 = 0; c2 < alphabet.length; c2++) {
      for (let c3 = 0; c3 < alphabet.length; c3++) {
        let word = "";
        word += alphabet[c1];
        word += alphabet[c2];
        word += alphabet[c3];
        words.push(word);
      }
    }
  }
words.sort();
console.log(words[k - 1]);

---

別解ですが、法則を見つけ、ソートなしで解きました。
二十六進法として考えました。

kの二十六進法のそれぞれの位の値を、
アルファベット３文字の左の位、真ん中の位、右の位として、
それぞれの値を、アルファベット配列のインデックスとすれば、
求めたいアルファベットが得られます。

別解

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

const k = Number(lines[0]);
const k26 = k.toString(26);//二十六進法に変換

const alphabet ="abcdefghijklmnopqrstuvwxyz";

//それぞれの位の値を十進法に戻し、アルファベット配列のインデックスにする

//左の文字
const left = alphabet[parseInt(k26[0], 26)];

//真ん中の文字
const center = alphabet[parseInt(k26[1], 26)];

//右の文字
const right = alphabet[parseInt(k26[2], 26) - 1];

console.log(left + center + right);

---

別解2

.toString(26)やparseInt(k26[0], 26)を使わずに解きました。
十進法が、百の位、十の位、一の位が0~9の値をとり、10で繰り上がるように、
二十六進法として、アルファベット小文字 3 文字を、左の文字の位、真ん中の文字の位、右の文字の位が0~25の値を取り、26で繰り上がる、と考えます。

別解2

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

const k = Number(lines[0]);
const alphabet ="abcdefghijklmnopqrstuvwxyz";

//右の文字
const right = alphabet[k % alphabet.length - 1];//アルファベット文字数26ごと -1

//真ん中の文字
const centerPlace = Math.trunc(k / alphabet.length);//真ん中の文字の位の値
const center = alphabet[centerPlace % alphabet.length];//アルファベット文字数26ごと

//左の文字
const leftPlace = Math.trunc(centerPlace / alphabet.length);//左の文字の位の値
const left = alphabet[leftPlace];//商だけ、余りは必要ない。k<=26^3より。

console.log(left + center + right);

右の文字の位は、1からはじまり25まで、26になったら繰り上がるので0になります。以降、0~25を繰り返します。
kをアルファベット26文字で割ったあまりを、アルファベット配列のインデックスで考えるので-1すれば求められます。

真ん中の文字の位は、0からはじまり、右の文字の位から26ごとに繰り上がって来ます。まず"kをアルファベット26文字で割った商"で、右の文字の位の繰り上がり回数を求めます。この商も、26ごとに繰り上がるので、さらにアルファベット26文字で割った余りで求められます。0からはじまっているので、そのままアルファベット配列のインデックスとして考えられます。

左の文字の位は、0からはじまり、真ん中の位から26ごとに繰り上がってくるので、
真ん中の位の"kをアルファベット26文字で割った商"が、何回繰り上がってきたか、アルファベット２６文字で割った商で求められます。
左の文字の位の値は,kの条件(1 ≦ k ≦ 17,576 (= 26^3 ))より、最大で25なので、繰り上がりはありませんから、余りを求める必要はなく、商だけで大丈夫です。