[CPE一星49題] UVA10420 - List of Conquests 題目解析與實作

作者： 中國醫藥大學蔡豐聲


編輯製作： 蔡豐聲、莊祺仁 

出品團隊： 中國醫藥大學 醫療資訊學系 程式俱樂部

 YT： https://youtu.be/F82yMKIETA0

## 題目資訊

  • 題目名稱： List of Conquests
  • 編號： CPE21924, UVA10420 

## 題目解析

當萊波雷羅（Leporello）依時間順序記錄下多尼‧喬凡尼（Don Giovanni）所「愛」的所有「美女」時，他在向他人展示主人的征服紀錄時遇到困難，因為每次都必須統計各國籍美女的人數。請協助萊波雷羅進行這項統計工作。

## 輸入說明

  • 輸入第一行含有一個數字 $n$，表示接下來會有 $n$ 行資料。

  • 之後的每一行（最多 75 個字元）由「國家」和「女子姓名」兩部分組成：

    1. 第一個單詞是國家名稱。
    2. 其餘所有單詞則構成該女子的名字。
    3. 您可以假設所有國家的名稱僅為一個單詞。

## 輸出說明

  • 輸出由按字母順序排列的行組成。

  • 每一行以國家名稱開頭，後面跟著該國家中多尼·喬凡尼「愛」的美女總數，兩者之間用空格分隔。

## 範例測試

  • 輸入：

                 3
                 Spain Donna Elvira
                 England Jane Doe
                 Spain Donna Anna
  • 輸出：

                 England 1
                 Spain 2

## 解題思路

  • Dictionary (字典數據結構)：

  1. 字典使用 key-value 的方式記錄資料：{"key": "value"}。
  2. 本題中，我們將國家名稱作為 key，出現次數作為 value，例如：{"England": 1, "Spain": 2}。

  • dict.get() 方法應用：
  1. 使用 dict.get(key, default) 讀取 key 對應的值；若 key 不存在，則回傳指定的預設值（default）。
  2. 當讀入一個國家名稱時，使用以下方式更新次數： dic[country] = dic.get(country, 0) + 1
  3. 當 key 尚未存在時：dic.get("England", 0) 會拿到預設值 `0`，加 `1` 後將字典更新為{"England": 1}。
  4. 當 key 已經存在時：會直接取得當前的累計次數並加 `1`。
  • sorted(dict) 排序：
  1. 使用 sorted(dict) 可以將字典所有的 key 取出並按照字母進行排序。
  2. 例如原字典為 {"Spain": 2, "England": 1}，經過 sorted() 處理後會得到 key 的排序列表 ["England", "Spain"]。
  3. 接著遍歷這個排序後的列表，即可依字母順序輸出每個國家及其對應的人數。

## 實作程式碼 (Python)

import sys

# 讀入 n
n = int(sys.stdin.readline())
country_counts = dict()
for _ in range(n):
    line = sys.stdin.readline()
    # 取第一個字串(country)
    country = line.split(" ")[0]
    # 更新 dictionary 次數
    country_counts[country] = country_counts.get(country, 0) + 1

# 將國家排序
for country in sorted(country_counts):
    print(country, country_counts[country])