区間ごとに分割していく処理は、ものすごく大事な典型処理なので、是非ともテンプレ化してノータイムで書けたらすごくいい感じ！！！！！
問題概要
"aabbbbccbaaa"
のような長さ N の文字列 S が与えられる。同じ文字が連続している区間が何個あるかを求めよ。
上記の例の場合、(a, 2) (b, 4), (c, 2), (b, 1), (a, 3) ということで答えは 5 となる。
制約
考えたこと
このように、文字列や数列に対して、同じ要素が連続しているところを切り出す処理は、様々な問題の前処理として極めてよくみる。
なので、このような処理をテンプレ化して自動的に実装できる状態にするととてもいいイメージ。たとえば下コードのように書ける。
- i は毎回区間の始まりを表す
- j = i からスタートして、S[ j ] != S[ i ] となる最初の j を探す
- i = j とする (次回の反復で、i は次の区間の開始位置になる)
という思想で実装している。
#include <iostream> #include <string> using namespace std; int main() { int N; string S; cin >> N >> S; int res = 0; for (int i = 0; i < N;) { int j = i; while (j < N && S[j] == S[i]) ++j; ++res; i = j; } cout << res << endl; }
