UVA10420 - List of Conquests

UVA10420 - List of Conquests

四月 06, 2019

題目簡述

輸入 t 個字串，每個字串開頭的第一個單字是一個國家
求每個國家出現的次數，輸出照字典序排列

初步想法

這個問題可以分成三個子問題

  1. 字串處理，怎麽將第一個單字切出來當做 key
  2. 怎麽統計每個 key 出現的次數
  3. 如何將統計好的資料結構按照字典序排列

第一個問題我的解決方法是讀整行之後塞到 stringstream 去做字串切割，即可簡單的將第一個單字分離出來。
第二個問題我使用 C++11 新增的 unordered_map 資料結構，他的底層實作是 hash table，搜尋和插入都只要 O(1) 的時間。
第三個問題我比較懶，我直接使用 vector 和 \<algorithm> 裡面的 sort 來實作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/*
 * UVA10420 - List of Comquests
 * Author: ifTNT
 */

#include <iostream>
#include <string>
#include <sstream>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int t;
    string buf;
    string contry;
    stringstream ssbuf;
    unordered_map<string, int> counter;
    vector<string> contryNames;
    cin >> t;
    cin.ignore();
    while(t--){
        ssbuf.str(string());
        getline(cin, buf);
        
        ssbuf << buf;
        ssbuf >> contry;

        if(counter.find(contry)!=counter.end()){
            counter[contry] += 1;
        }else{
            counter.insert(make_pair(contry,1));
            contryNames.push_back(contry);
        }
    }
    sort(contryNames.begin(), contryNames.end());
    for(auto i:contryNames){
        cout << i << " " << counter[i] << endl;
    }
    return 0;
}

還可以更快嗎

待補