C++で数値の傾きを求めるアルゴリズムを解説

問題の概要

この記事では、ある数値 N が与えられたときに、その「傾き（スロープ）」を求める方法をC++で解説します。

数値の傾きとは？

数値の傾きとは、その数値に含まれる極大桁（maxima）と極小桁（minima）の合計数のことを指します。

• 極大桁：直前と直後の両方の隣接する桁よりも大きい桁
• 極小桁：直前と直後の両方の隣接する桁よりも小さい桁

なお、先頭と末尾の桁には隣接する桁が2つ存在しないため、判定対象からは除外されます。

具体例で理解しよう

入力：

N = 9594459

出力：

2

この例では、2番目の桁「5」が両隣の「9」よりも小さい極小桁、3番目の桁「9」が両隣の「5」と「4」よりも大きい極大桁に該当するため、傾きは 2 となります。

解法のアプローチ

この問題に対するシンプルな解決策は、最初と最後の桁を除いて、各桁を1つずつ走査することです。各桁について、直前と直後の桁と大小関係を比較し、極大桁または極小桁に該当するかどうかを判定します。最後に、それらの合計カウントを返せば完成です。

この手法の計算量は O(N) であり、数値を1回走査するだけで済むため非常に効率的です。

C++での実装例

以下は、この解法の動作を示すサンプルプログラムです。

#include <iostream>
using namespace std;

int findNumberSlope(string N, int len) {
    int slope = 0;
    for (int i = 1; i < len - 1; i++) {
        if (N[i] > N[i - 1] && N[i] > N[i + 1])
            slope++;  // 極大桁
        else if (N[i] < N[i - 1] && N[i] < N[i + 1])
            slope++;  // 極小桁
    }
    return slope;
}

int main() {
    string N = "574473434329";
    int len = N.size();
    cout << "The slope of the given number is " << findNumberSlope(N, len);
    return 0;
}

実行結果

The slope of the given number is 7

まとめ

数値の傾きを求める問題は、文字列として数値を扱い、隣接する桁との大小比較を繰り返すだけで解決できます。計算量は O(N)、空間計算量も O(1) とシンプルで効率的なアルゴリズムなので、競技プログラミングやコーディング面接の練習にも最適な題材です。