AtCoder ABC 155 C - Poll (5Q, 灰色, 300 点)

連想配列が有効活用できる問題

• 問題へのリンク

問題概要

個の文字列 がある。

登場回数の最も多い文字列を、辞書順に出力せよ。

制約

• 
• 

考えたこと

各文字列がそれぞれ何個あるのかを求めたい。そこで、次のような配列を作りたい。

---

• nums[str]：文字列 str の登場個数

---

ここで、配列の添字が「文字列」となっている。このように、整数値以外のさまざまな値も添字にできるようにしたものを連想配列などと呼ぶことがある。

C++ では、map<(添字の型), (配列の値の型)> で実現できる。特に今回は map<string, int> 型で実現できる。

各文字列の個数がわかれば、最多のものを全て求めて、それらを辞書順に求めればよい。

コード

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

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

    // 連想配列 num
    map<string, int> nums;
    for (int i = 0; i < N; i++) {
        cin >> S;
        nums[S]++;
    }

    // 最大個数を求める
    int max_num = 0;
    vector<string> max_str;
    for (auto [str, num] : nums) {
        if (max_num < num) {
            max_num = num;
            max_str = {str};
        } else if (max_num == num) {
            max_str.push_back(str);
        }
    }

    // 出力
    sort(max_str.begin(), max_str.end());
    for (auto str : max_str) cout << str << endl;
}