《アルゴリズムを学ぶ》10.Map（辞書）

# Overview
辞書（Map / Dictionary / HashMap） は キーと値のペア を持つデータ構造。
[1.Pythonの辞書の基本](#1-pythonの辞書の基本)
[2.辞書の応用](#2-辞書の応用)
[3.典型問題を解いてみる](#3-典型問題を解いてみる)

# 1. Pythonの辞書の基本
Python では`dict`を使うと キーと値のペア を簡単に管理できる。
データの管理、検索、カウント、グループ化などに広く使われ、競技プログラミングでは 頻度カウント・素早いデータ検索・グループ管理 に必須。

|操作名	|説明	|Python の辞書操作|
|--|--|--|
|追加・更新	|キーに値を設定	|`dict[key] = value`|
|取得（get）	|キーの値を取得（キーがない場合も対応）	|`dict.get(key, default)`|
|削除（pop / del）	|キーを削除	|`dict.pop(key)` / `del dict[key]`|
|キーの存在確認（in）	|キーが辞書に存在するか	|`key in dict`|
|キー一覧（keys）	|すべてのキーを取得	|`dict.keys()`|
|値一覧（values）	|すべての値を取得	|`dict.values()`|
|キーと値一覧（items）	|キーと値のペアを取得	|`dict.items()`|


**＜基本実装＞**
```python
# 辞書の作成と基本操作
data = {"apple": 3, "banana": 5, "cherry": 2}

data["banana"] = 7  # 値を更新
data["grape"] = 4  # 新しいキーを追加
print(data.get("orange", 0))  # 存在しないキーの取得（デフォルト値）

del data["apple"]  # キーを削除
print("banana" in data)  # キーの存在確認
print(list(data.keys()))  # キー一覧
print(list(data.values()))  # 値一覧
print(list(data.items()))  # キーと値のペア一覧
```

# 2. 辞書の応用
### (1) 頻度カウント
リスト内の要素が 何回出現したかをカウント する。
```python
from collections import Counter

arr = ["apple", "banana", "apple", "cherry", "banana", "banana"]
counter = Counter(arr)

print(counter)  # Counter({'banana': 3, 'apple': 2, 'cherry': 1})
print(counter["banana"])  # 3
```
ポイント:
・Counter を使うと頻度カウントが簡単
・`dict`でもカウント可能
```python
freq = {}
for item in arr:
    freq[item] = freq.get(item, 0) + 1
```
    
### (2) 2つのリストを辞書に変換
```python
keys = ["apple", "banana", "cherry"]
values = [3, 5, 2]

fruit_dict = dict(zip(keys, values))
print(fruit_dict)  # {'apple': 3, 'banana': 5, 'cherry': 2}
```
ポイント:
・zip() を使うとキーと値のペアを簡単に作れる

### (3) グループ化
リスト内のデータを特定のキーでグループ化する。
```python
data = [("apple", 3), ("banana", 5), ("apple", 7), ("banana", 2)]
grouped = {}

for key, value in data:
    if key not in grouped:
        grouped[key] = []
    grouped[key].append(value)

print(grouped)  # {'apple': [3, 7], 'banana': [5, 2]}
```
ポイント:
辞書を使うとカテゴリごとにデータを整理できる

### (4) defaultdict を使う
```python
from collections import defaultdict

data = [("apple", 3), ("banana", 5), ("apple", 7)]
grouped = defaultdict(list)

for key, value in data:
    grouped[key].append(value)

print(grouped)  # {'apple': [3, 7], 'banana': [5]}
```
ポイント:
・キーが存在しないときのデフォルト値を設定できる

# 3. 典型問題を解いてみる

### 例題1. 頻度カウント
**問題: N 個の単語が与えられる。それぞれの単語が何回登場したかを出力せよ。**
> [参考： ABC315 B - Word Frequency](https://atcoder.jp/contests/abc315/tasks/abc315_b)
<details><summary> 回答　</summary>

```python
from collections import Counter

N = int(input())
words = [input() for _ in range(N)]

counter = Counter(words)
for word, count in counter.items():
    print(word, count)
```
</details>

### 例題2. 2つのリストを辞書に変換
**問題: N 個のキーと値のペアが与えられる。辞書を作成し、指定されたキーの値を出力せよ。**
> [参考： ABC318 B - Key Value Map](https://atcoder.jp/contests/abc318/tasks/abc318_b)
<details><summary> 回答　</summary>

```python
N = int(input())
mapping = {}

for _ in range(N):
    key, value = input().split()
    mapping[key] = value

Q = int(input())
for _ in range(Q):
    query = input()
    print(mapping.get(query, "Not Found"))
```
</details>

### 例題3. グループ化
**問題: N 個のデータが与えられる。それぞれのカテゴリごとにデータをグループ化して出力せよ。**
> [参考： ABC319 C - Grouping Data](https://atcoder.jp/contests/abc319/tasks/abc319_c)
<details><summary> 回答　</summary>

```python
N = int(input())
grouped = {}

for _ in range(N):
    category, value = input().split()
    if category not in grouped:
        grouped[category] = []
    grouped[category].append(value)

for category, values in grouped.items():
    print(category, *values)
```
</details>

### 例題4. 辞書を使った最頻値の検索
**問題: N 個の数値が与えられる。最も頻繁に出現する数値を出力せよ。**
> [参考： ABC320 B - Most Frequent Number](https://atcoder.jp/contests/abc320/tasks/abc320_b)
<details><summary> 回答　</summary>

```python
from collections import Counter

N = int(input())
numbers = list(map(int, input().split()))

counter = Counter(numbers)
most_common = counter.most_common(1)[0][0]  # 最頻値
print(most_common)
```
</details>

### 例題5. 文字列のカウント
**問題: 文字列 S が与えられる。各文字の出現回数を出力せよ。**
> [参考： ABC322 C - Character Count](https://atcoder.jp/contests/abc322/tasks/abc322_c)
<details><summary> 回答　</summary>

```python
from collections import Counter

S = input()
counter = Counter(S)

for char, count in sorted(counter.items()):
    print(char, count)
```
</details>