https://www.geeksforgeeks.org/leaders-in-an-array/
より
問題
配列の中のリーダーとなる数字を見つけなさい。
リーダーとなるとはその要素の右側にその要素以下の数字がない要素とする。
例
[16, 17, 4, 3, 5, 2]
=> [17, 5]
解答
さてあんまり難しいことは考えずに普通に実装してみましょう。
上記図のように要素ごとそれ以降の要素全てと比べてみて数値を比較して大きな数値がなければその数をリーダーにすれば良さそうです。
簡単ですね。実装してみましょう。
function findLeaderNumbers(arr) {
const res = []
for(let i = 0; i < arr.length - 1; i++) {
let isLeader = true
for(let j = i + 1; j < arr.length; j++) {
if(arr[i] <= arr[j]) {
isLeader = false
}
}
if(isLeader) {
res.push(arr[i])
}
}
return res
}
さてこのコードはロープの中にループが存在します。このときこのコードは最適なコードと言えるでしょうか？
計算量を考えてみる
このアルゴリズムはループが二つネストされているため配列の大きさをNとするとO(n*n)の計算量と言えます。
O記法とは何か
- プログラムがどれくらいの計算量を必要としているかの指標
- 入力された変数の数に対してプログラムのステップ数がどれだけ変わるかを式に表すことで表現できる
- 大体のケースで入力の配列の長さをnと定義する。なので配列を一回回すだけだったらO(n)、ループがネストするならO(n*n)
wikipediaより
さて今回のこの問題O(n*n)より効率的な方法はないでしょうか？
実はO(n)で解ける方法があります。難しいアルゴリズムとかを知っておく必要はありません。
O(N)の解法
よくこの問題をみてみると右から配列をみていけばより効率的にリーダーを探せることに気づくかと思います。
以下のように右からの探索で
右からの最大値を変数に保持しておけば一回配列を探索するだけで問題を解くことができます
実装
function findLeaderNumbers(arr) {
let prevMax = arr[arr.length - 1]
const res = [prevMax]
for(let i = arr.length - 2; i >= 0; i--) {
if(arr[i] > prevMax) {
prevMax = arr[i]
res.push(arr[i])
}
}
return res
}
まとめ
これが競技プログラミング？と言えるかどうかわかりませんが、プログラミングの問題は難しい数学やアルゴリズムの知識がないと立ち向かえないと思われるかたもいらっしゃると思います。また実務のコーディングとは全く違うと考える方もいるかと思います。
僕自身そうでしたが、この問題を１年前にやってみてプログラミングの問題って結局お題を解釈してそれを達成するために自分の知識を最大限使って効率よくプログラムを実装するってことなんですよね。
仕様をきちんと解釈して自分たちのチームでいかに効率よくその問題に対処するかって話で、そこにはもちろん難しい知識が必要な場合もありますが、基本は自分の頭で考えて行動・実装していく、これってまさに実務でやってることと同じではないでしょうか。ぁ人間関係の問題とか仕様の方を捻じ曲げるとかいろんなことはできるにせよ）
ということでプログラミングの問題解くの好きになって僕ですが、まだまだ全然実力無くて多分中学生とかにも余裕で負けるレベルなのでもっと頑張っていきたいと思います。