paiza×Qiitaコラボキャンペーン、もう少しで終わりますね。
最後に一つ面白そうな問題を見つけたので解いてみます。
paiza問題ランクB Final問題の「名刺バインダー管理」になります。
※問題文はリンクより参照してください。
解き方
以下の流れに沿って解いていきます。
- 面裏のバインダー番号配列作成
- 再帰関数で検索数値が含まれているバインダー番号配列があるまで繰り返す
- 検索数値が含まれていれば現在のバインダー番号配列を返却
- バインダー番号配列から検索番号の位置を特定
- 配列最後から検索番号の裏側の値を取得 <- これが目的
あとはこれをコードに書き写せばいいですね。
完成コード
別段難しいことはしていませんが、再帰関数の使い方がコツでしょうか。次々とバインダー番号配列を作成し、検索番号があるまで繰り返すようにしています。
目的は配列最後から検索番号の裏側の値を取得することなので、binder[(binder.length - 1) - index]としています。配列最後のインデックスから検索番号のインデックスを引き、裏側の値を取得しています。
const [n, m] = lines[0].split(' ').map(v => +v);
function binderExamination (start, end) {
const binder = [];
// 面裏のバインダー番号配列作成
for (let i = start; i <= end; i++) {
binder.push(i);
}
// 検索数値が含まれていれば現在のバインダー番号配列を返却
if (binder.includes(m)) {
return binder;
}
const maxBinderValue = binder[binder.length - 1];
// 再帰関数で検索数値が含まれているバインダー番号配列があるまで繰り返す
return binderExamination(maxBinderValue + 1, maxBinderValue + (n * 2));
}
const binder = binderExamination(1, n * 2);
// バインダー番号配列から検索番号の位置を特定
const index = binder.indexOf(m);
// 配列最後から検索番号の裏側の値を取得
console.log(binder[(binder.length - 1) - index]);
さいごに
問題が面白いと解きがいがありますね。
これはあくまで自分の解き方です。もっといいアルゴリズムがあるなどありましたら教えていただきたいです。
Comments
上記、
recursionではなくbinderExaminationではありませんか？あと、問題では
n、mの範囲はともに1～100000という条件が設定されていますが、例えばnを1、mを100000としてもエラーを出さずに処理できますでしょうか。Let's comment your feelings that are more than good