C++競プロ学習日記(仮)

( 学習記録であり解説Blogではないです )

No.676 C0nvertPr0b1em|yukicoder|std::replace_if

C++ の algorithm ヘッダにある std::replace_if を初めて使って解いたのでメモ。

解いた問題:No.676 C0nvertPr0b1em - yukicoder ★1


題意

  • 英文字列 S が与えられる。
  • S に含まれる英字  I,l を 数字の  1 に、 O,o を 数字の  0 に置き換えたものを出力する。
  •  |S| \leq 10^3


考察

特定の英字を探し、一致したら数字に置き換えるという易しい問題です。
loop で一文字ずつ見ていっても解けますが、今回は std::replace_if を使って解きました。

std::replace_if は、「条件を満たす要素を指定された値に置き換える。*1 」という機能を提供するSTLです。

std::replace_if( 検索開始位置, 検索終了位置, 置換条件, 置換する値 )

同じような STLstd::replace *2 がありますが、std::replace の場合、「指定された値と一致する要素を指定された値に置き換える」ことしか出来ません。( e.g. 文字列に含まれた全ての A を 1 に置換する...など )
ですので、今回の問題のように置換したい条件がある場合は、std::replace_if を使うと第三引数( 置換条件 )にラムダ式 *3 を使えて便利です。

第三引数に使うラムダ

// 文字が I, または l のとき true を返す
[]( const char &c ){ return c == 'I' || c == 'l'; }

// 文字が O, または o のとき true を返す
[]( const char &c ){ return c == 'O' || c == 'o'; }

注意点として、今回は英字を数字に置換するので、置換する数字の方を第四引数で指定するとき同じ char 型で渡す必要があります。

第四引数は置換する要素と同じ型にする

replace_if( ALL( S ), []( const char &c ){ return c == 'I' || c == 'l'; }, '1' );
replace_if( ALL( S ), []( const char &c ){ return c == 'O' || c == 'o'; }, '0' );

 


コード

#include <bits/stdc++.h>
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
int main()
{
    string S;
    cin >> S;
    replace_if( begin( S ), end( S ), []( const char &c ){ return c == 'I' || c == 'l'; }, '1' );
    replace_if( begin( S ), end( S ), []( const char &c ){ return c == 'O' || c == 'o'; }, '0' );
    cout << S << endl;
    return 0;
}

提出:https://yukicoder.me/problems/no/676
別解:https://yukicoder.me/submissions/255892 ( loop解 )
 


計算量

std::replace_if の計算量は 「正確に last - first 回の述語の適用を行う。」となっている。
この問題の場合、文字数分の比較(条件判定)が発生するので、std::replace_if 1 回の走査につき  O(|S|).
全体では  O(|S|) となる。


参考