JOI 一次予選 2021 (第 1 回) B - JOI ソート (7Q, 難易度 2)

これは面白い！

• 問題へのリンク

問題概要

文字 J, O, I からなる、長さ の文字列 が与えられる。

の文字を並び替えて、次の条件を満たすものを求めよ。

• すべての文字 J は、すべての文字 O よりも前にある
• すべての文字 O は、すべての文字 I よりも前にある
• すべての文字 J は、すべての文字 I よりも前にある

解法

次のようにすればよい。

• 文字列 の中の文字 J の個数 Jnum を求める
• 文字列 の中の文字 O の個数 Onum を求める
• 文字列 の中の文字 I の個数 Inum を求める

これらは for 文で求められます。これらを求めたあと、次のようにすればよいでしょう。

• 文字 J を Jnum 個並べる
• 文字 O を Onum 個並べる
• 文字 I を Inum 個並べる

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    string S;
    cin >> N >> S;

    int Jnum = 0, Onum = 0, Inum = 0;
    for (int i = 0; i < N; ++i) {
        if (S[i] == 'J') ++Jnum;
        else if (S[i] == 'O') ++Onum;
        else ++Inum;
    }

    // 出力する
    for (int i = 0; i < Jnum; ++i) cout << 'J';
    for (int i = 0; i < Onum; ++i) cout << 'O';
    for (int i = 0; i < Inum; ++i) cout << 'I';
}