Pythonで解く「身長チェッカー」問題：正しい位置にいない生徒の人数を数える方法

問題の概要

あるグループの生徒たちが、記念撮影のために身長の低い順（非減少順）に並ばなければならないとします。生徒の身長を格納した配列が与えられたとき、正しい位置に立っていない生徒の最小人数を返すのがこの問題の目的です。

例えば、配列が [1, 1, 4, 2, 1, 3] の場合、答えは 3 になります。身長が 4 の生徒、身長が 3 の生徒、そして最後の身長 1 の生徒の合計 3 人が正しい位置に立っていないためです。

解法のアプローチ

この問題は非常にシンプルで、次の手順で解くことができます。

• 答えを格納する変数 answer を 0 で初期化する
• 元の配列を昇順にソートした配列 x を作成する
• 元の配列をそのまま y として保持する
• i を 0 から配列の長さ - 1 までループさせる
  • x[i] と y[i] が異なる場合、answer を 1 増やす
• answer を返す

つまり「ソート済みの配列と元の配列を要素ごとに比較し、一致しない箇所の数を数える」というのが核心的なアイデアです。一致しない位置こそが、並び替えが必要な生徒の位置に他なりません。

実装例

それでは、理解を深めるために Python での実装例を見ていきましょう。

class Solution(object):
    def heightChecker(self, heights):
        ans = 0
        x = sorted(heights)   # ソート済みの配列
        y = heights           # 元の配列
        for i in range(len(x)):
            if x[i] != y[i]:
                ans += 1
        return ans

ob1 = Solution()
print(ob1.heightChecker([1, 1, 4, 2, 1, 3]))

入力

[1, 1, 4, 2, 1, 3]

出力

3

計算量について

この解法の時間計算量は、ソート処理が支配的となるため O(n log n) です。また、ソート済みのコピーを作成するため、空間計算量は O(n) となります（n は配列の長さ）。シンプルで直感的な実装であり、多くの場合において十分に実用的なアプローチです。

まとめ

「身長チェッカー」問題は、ソートした結果と元の配列を比較するだけで解ける、アルゴリズムの基礎を確認するのに最適な練習問題です。配列操作や比較処理の復習として、ぜひ自分でも一度実装してみてください。