AtCoder ABC 261 C - NewFolder(1) (5Q, 灰色, 300 点)

連想配列（辞書）の練習問題！

• 問題へのリンク

問題概要

文字列 が与えられる。

各 に対して、

• となる が存在しない場合は をそのまま出力せよ
• となる が存在する場合は、その個数を としたとき、 に "(k)" を付して出力せよ

制約

• 
• 

考えたこと

問題文で言われたままに処理すればよいが、次の情報を保持しておこう。

---

• num[str]：今までみてきた文字列の中に、文字列 str に一致するものが何個あるか

---

このように、配列の添字に「文字列」のようなものを格納したいときには連想配列を活用できる。

C++ であれば、map<(添字の型), (配列の値の型)> という型が使える。とくに今回は map<string, int> 型が使える。なお、この連想配列の要素のアクセスに要する計算量は である（ は文字列の長さ）。

よって、全体の計算量は、与えられる文字列のサイズの最大値を として、 と評価できる。

コード

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

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

    map<string, int> num;  // 連想配列の値はデフォルトで 0 になる
    for (int i = 0; i < N; i++) {
        cin >> S;
        if (!num.count(S)) {
            // S が初出のとき
            cout << S << endl;
        } else {
            // S がすでに出ているとき
            cout << S << "(" << num[S] << ")" << endl;
        }

        // S をカウントする
        num[S]++;
    }
}