C++でN個の磁石から形成される磁石グループの数を求める方法

数字 1 は正極（N極）を、0 は負極（S極）を表します。

各磁石は 10 または 01 のように2つの極を持っています。互いに引き合う磁石同士でグループが形成され、異なる極が向かい合っている磁石は同じグループに属します。

ここでは、N個の磁石が与えられます。あなたの課題は、これらの磁石から何個のグループが形成されるかを求めることです。

隣り合う2つの磁石が異なる場合、その場所で新しいグループが始まります。このとき、グループのカウントを1つ増やしていきます。

具体例を見てみましょう。

入力

magnets = ["10", "01", "01", "01", "10", "01"]

出力

4

隣り合う磁石が異なるたびに新しいグループが形成されるため、この配列では「10」と「01」の並びが切り替わる箇所が3つあります。最初のグループを1と数えると、グループの総数は4となります。

アルゴリズム

• 磁石の配列を初期化します。
• ペアとして扱うため、カウントを1で初期化します。
• インデックス1から配列の末尾まで繰り返すループを作成します。
• 現在の磁石が直前の磁石と異なる場合は、カウントを1増やします。
• 最後にカウントを返します。

実装

以下は、上記のアルゴリズムをC++で実装したコードです。

#include <bits/stdc++.h>
using namespace std;
int getMangetGroupsCount(string magnets[], int n) {
    int count = 1;
    for (int i = 1; i < n; i++) {
        if (magnets[i] != magnets[i - 1]) {
            count++;
        }
    }
    return count;
}
int main() {
    string magnets[] = { "10", "01", "01", "01", "10", "01" };
    int n = 6;
    cout << getMangetGroupsCount(magnets, n) << endl;
    return 0;
}

出力

上記のコードを実行すると、次の結果が得られます。

4